FastPrepFastPrep
Problem Brief

Array Reduction Algorithm

INTERNOA
See Snowflake online assessment and hiring insights

The developers of Hackerland are working on an array reduction algorithm that takes in an array of n integers say arr and does the following until the array arr is empty:

  • Initialize an array result as an empty array
  • Choose an integer k such that 1 ≤ k ≤ length of the array
  • Append the MEX of the first k elements of the array arr to the array result
  • Remove first k elements of the array arr

    • Given an array arr, find the lexicographically maximum array result that can be obtained using the above algorithm.

    Note:

  • An array x is lexicographically greater than an array y if in the first position where x and y differ xi > yi or if |x| > |y| and y is a prefix of x (where |x| denotes the size of the array x).
  • The MEX of a set of non-negative integers is the minimal non-negative integer such that it is not in the set. For example, MEX({1,2,3}) = 0 and MEX({0,1,2,4,5}) = 3.

    • 1Example 1

    Input
    arr = [0,1,1,0]
    Output
    [2,2]
    Explanation
    Given n = 4, arr = [0,1,1,0], one of the optimal ways to make array result lexicographically maximum is as follows -
  • Take k = 2, the MEX of the 1st and 2nd element of arr is 2. So arr = [1,0] and result = [2].
  • Take k = 2, the MEX of the 1st and 2nd element of arr is 2. So arr = [] and result = [2,2].
    • arr is now empty and the answer is [2,2].

    Constraints

    Limits and guarantees your solution can rely on.

  • 1 <= n <= 10^5
  • 0 <= arr[i] <= n
    • public int[] arrayReductionAlgorithm(int[] arr) {
    // write your code here
}
    Input

    arr

    [0,1,1,0]

    Output

    [2,2]

    Sign in to submit your solution.