FastPrepArray Reduction Algorithm

Array Reduction Algorithm

Snowflake logoSnowflake● HardINTERNOA
Learn

Problem statement

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.

Function

arrayReductionAlgorithm(arr: int[]) → int[]

Examples

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

See Snowflake hiring insights
public int[] arrayReductionAlgorithm(int[] arr) {
    // write your code here
}
arr[0,1,1,0]
expected[2,2]
Checking account…