Array Reduction Algorithm
Updated
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
resultas an empty array - Choose an integer
ksuch that1 ≤ k ≤ length of the array - Append the MEX of the first
kelements of the arrayarrto the arrayresult - Remove first
kelements of the arrayarr
Given an array arr, find the lexicographically maximum array result that can be obtained using the above algorithm.
Note:
- An array
xis lexicographically greater than an arrayyif in the first position wherexandydifferxi > yior if|x| > |y|andyis a prefix ofx(where|x|denotes the size of the arrayx). - 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 ofarris 2. Soarr = [1,0]andresult = [2]. - Take
k = 2, the MEX of the 1st and 2nd element ofarris 2. Soarr = []andresult = [2,2].
arr is now empty and the answer is [2,2].
Constraints
- 1 <= n <= 10^5
- 0 <= arr[i] <= n
More Snowflake interview questions
- Connect Four from the Last MovePHONE SCREEN · Seen Nov 2026
- Minimum Edits to a Perfect Binary TreePHONE SCREEN · Seen Nov 2026
- Parallel Courses IIIONSITE INTERVIEW · Seen Nov 2026
- Safest Shortest Path Through a GridOA · Seen Nov 2026
- Configurable Per-Client Token BucketsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Find Valid SET Card TriplesOA · PHONE SCREEN · Seen Nov 2026
- LFU CacheOA · ONSITE INTERVIEW · Seen Nov 2026
- Minimum Index Distance Between Person and CakeOA · PHONE SCREEN · Seen Nov 2026
- Minimum N-ary Tree Depth DeletionsOA · PHONE SCREEN · Seen Nov 2026
- Sum of Binary Tree Boundary NodesOA · PHONE SCREEN · Seen Nov 2026
Similar questions at other companies
- Minimum Rounds to Complete All TasksInfosys · OAInfosys interview questions
- Minimum Distinct Prefix CostChubb · OAChubb interview questions
- Minimum Distinct Prefix CostGoldman Sachs · OAGoldman Sachs interview questions
- Maximum Distinct Values After SwapsAkuna Capital · OAAkuna Capital interview questions
- Rearrange Songs by AuthorZomato / Eternal · OAZomato / Eternal interview questions
- 🐘 Keep Them Apart 🦙QRT · OA
- Minimum Operations to Make Array ValidAmazon · OA
- Min Cost to Complete All ProjectsSalesforce · OASalesforce interview questions
- Freelancing PlatformJP Morgan Chase · OAJP Morgan Chase interview questions
- Maximum Distinct Values After Cross-Array SwapsScale AI · OAScale AI interview questions