You are given an integer array nums.
You want to construct an array result by repeatedly performing the following operation until nums becomes empty:
k such that 1 <= k <= len(nums).k elements of nums.result.k elements from nums.Return the lexicographically maximum array result that can be obtained after performing the operations.
The MEX of an array is the smallest non-negative integer not present in the array.
An array a is lexicographically greater than an array b if in the first position where a and b differ, array a has an element that is greater than the corresponding element in b. If the first min(a.length, b.length) elements do not differ, then the longer array is the lexicographically greater one.
Example 1:
Input: nums = [0,1,0]
Output: [2,1]
Explanation:
k = 2 elements [0, 1] which has MEX = 2. Current result = [2].[0] has MEX = 1. Thus, the final result = [2, 1].Example 2:
Input: nums = [1,0,2]
Output: [3]
Explanation:
k = 3 elements [1, 0, 2] which has MEX = 3.nums is now empty. Thus, the final result = [3].Example 3:
Input: nums = [3,1]
Output: [0,0]
Explanation:
k = 1, first element [3] has MEX = 0. Current result = [0].[1] has MEX = 0. Thus, the final result = [0, 0].
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 105Problem Overview: You are given an array and must construct a new array of MEX values such that the result is lexicographically maximum. At every step you choose elements in a way that maximizes the current MEX while still allowing the remaining positions to be valid.
Approach 1: Brute Force Simulation (O(n²) time, O(n) space)
The straightforward method simulates every step. For each position, try removing each candidate element, recompute the MEX of the remaining multiset, and pick the option that produces the largest value for the current position. Computing the MEX requires scanning from 0 upward while tracking frequencies. This approach quickly becomes expensive because every step recomputes frequencies and MEX from scratch, leading to quadratic complexity.
Approach 2: Greedy with Frequency Map and Dynamic MEX (O(n log n) time, O(n) space)
A better solution keeps a frequency table of values and maintains the current MEX dynamically. Use a set or priority structure to track which numbers are missing from the current multiset. While iterating through the array, simulate removing elements and update frequencies. When a value’s frequency drops to zero, it becomes a candidate for the MEX. By always choosing the removal that preserves the highest possible MEX, you build the lexicographically maximum sequence. Set operations cost O(log n), producing an overall O(n log n) runtime.
Approach 3: Greedy with Frequency + Pointer MEX (O(n) time, O(n) space)
The optimal approach avoids ordered structures entirely. Maintain a frequency array for all numbers and a pointer representing the current MEX. First count all occurrences. Then process the array while decreasing frequencies as elements are considered removed. Each time a frequency becomes zero and the value is smaller than the current MEX pointer, adjust the pointer by moving forward until you reach the next missing value. This works because the MEX only increases when all smaller numbers are still present in the remaining multiset. The greedy rule ensures the resulting sequence stays lexicographically maximal while updating the MEX in amortized O(1) time.
Understanding how MEX behaves under insertions and removals is the key insight. Once every number from 0 to k-1 exists, the MEX becomes k. When one of those disappears, the MEX can drop immediately. Efficient solutions therefore track frequencies and the smallest missing number rather than recomputing the MEX repeatedly. Problems built around MEX commonly rely on greedy reasoning and prefix processing similar to tasks in greedy algorithms, array processing, and hash map frequency counting.
Recommended for interviews: Start by describing the brute force idea to show understanding of how the MEX changes after removals. Then move to the greedy frequency-based approach. Interviewers typically expect the O(n) frequency + pointer solution because it demonstrates strong reasoning about invariants and efficient MEX maintenance.
Solutions for this problem are being prepared.
Try solving it yourself| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n²) | O(n) | Useful for understanding how MEX changes after each removal |
| Greedy with Set Tracking Missing Values | O(n log n) | O(n) | When using ordered sets or priority structures to maintain MEX |
| Greedy with Frequency Array + Pointer MEX | O(n) | O(n) | Optimal approach for large inputs and interview settings |
Practice Lexicographically Maximum MEX Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor