Company: Juspay_29aug
Difficulty: medium
Array Reduction 4 Problem Description Developers are working on an optimal array algorithm that processes an array of n integers, referred to as arr , using the following steps until the array is empty: Initialize an empty array called result . Select an integer k such that 1 <= k <= length of the array arr . Append the MEX (Minimum Excluded Value) of the first k elements of arr to the result array. Removes the first k elements from arr . Given an array arr , determine the lexicographically largest result array that can be obtained using the algorithm. Definitions: An array x is lexicographically greater than an array y if either: At the first position where x and y differ, x[i] > y[i] |x| > |y| and y is a prefix of x (where |x| denotes the length of array x ). The MEX of a set of non-negative integers is the smallest non-negative integer not present in the set. For example, MEX({2,3,0}) = 1 and MEX({0,1,2,4,5}) = 3. Detailed Example of Algorithm: Given n = 4 , arr = [0,1,0