FastPrep

Description

Solutions

Array Reduction Algorithm

🤘 INTERN📚RELATED PROBLEMS

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 x_i > y_i 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.

Example 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:

1 <= n <= 10^5

0 <= arr[i] <= n