FastPrep
Problem · Heap

Product of the Maximum and Minimum in a Dataset

Learn this problem
● EasyGoldman SachsINTERNFULLTIMEOA

Problem statement

Starting with an empty set of integers named elements, perform the following query operations:

  • The command push x inserts the value of x into elements.
  • The command pop x removes the value of x from elements.

The integers in elements need to be ordered in such a way that after each operation is performed, the product of the maximum and minimum values in the set can be easily calculated.

Function

maxMin(operations: String[], x: int[]) → int[]

Complete the function maxMin in the editor below.

maxMin has the following parameter(s):

  • s[n]: an array of operations strings
  • int x[n]: an array of x where x[i] goes with operations[i].

Returns

int[n]: an array of long integers that denote the product of the maximum and minimum of elements after each query

Examples

Example 1

operations = ["push", "push", "push", "pop"]x = [1, 2, 3, 1]return = [1, 2, 3, 6]

Visualize elements as an empty multiset, elements = {}, and refer to the return array as products. The sequence of operations occurs as follows:

  1. push 1 → elements = {1}, so the minimum = 1 and the maximum = 1. Then store the product as products[0] = 1 × 1 = 1.
  2. push 2 → elements = {1, 2}, so the minimum = 1 and the maximum = 2. Then store the product as products[1] = 1 × 2 = 2.
  3. push 3 → elements = {1, 2, 3}, so the minimum = 1 and the maximum = 3. Then store the product as products[2] = 1 × 3 = 3.
  4. pop 1 → elements = {2, 3}, so the minimum = 2 and the maximum = 3. Then store the product as products[3] = 2 × 3 = 6.

Return products = [1, 2, 3, 6]

Constraints

  • 1 ≤ n ≤ 10^5
  • 1 ≤ x[i] ≤ 10^9
  • It is guaranteed that each operations[i] is either push or pop.
  • It is guaranteed that any value popped will exist in the array.

More Goldman Sachs problems

drafts saved locally
public int[] maxMin(String[] operations, int[] x) {
    // write your code here
}
operations["push", "push", "push", "pop"]
x[1, 2, 3, 1]
expected[1, 2, 3, 6]
checking account