FastPrep
Problem · Greedy

Array Reduction Algorithm

● HardSnowflakeINTERNOA
See Snowflake 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.

    • Examples
    01 · Example 1
    arr = [0,1,1,0]
return = [2,2]
    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
  • 1 <= n <= 10^5
  • 0 <= arr[i] <= n
    • More Snowflake problems
    drafts saved locally
    public int[] arrayReductionAlgorithm(int[] arr) {
    // write your code here
}
    arr[0,1,1,0]
    expected[2,2]
    sign in to submit