FastPrepMaximum MEX by Decreasing Values

Maximum MEX by Decreasing Values

IMC Trading logoIMC Trading● MediumNEW GRADOA
Learn

Problem statement

You are given an integer array arr. One operation replaces any element arr[i] by an integer x satisfying 0 <= x <= arr[i]. You may perform any number of operations.

The MEX of an array is the smallest nonnegative integer absent from it. Return the maximum MEX achievable after these operations.

Function

getMaximumMEX(arr: int[]) → int

Examples

Example 1

arr = [3,2,3]return = 3

Each element can supply any nonnegative number no greater than its original value. Build the longest prefix of distinct values starting at 0.

Example 2

arr = [0,1,1,3]return = 3

Each element can supply any nonnegative number no greater than its original value. Build the longest prefix of distinct values starting at 0.

Example 3

arr = [0,0,0]return = 1

Each element can supply any nonnegative number no greater than its original value. Build the longest prefix of distinct values starting at 0.

Constraints

  • 1 <= arr.length <= 2 * 10^5
  • 0 <= arr[i] <= 10^9

More IMC Trading problems

See IMC Trading hiring insights
public int getMaximumMEX(int[] arr) {
    // Write your solution here.
}
arr[3,2,3]
expected3
Checking account…