Lexicographically Maximum MEX Array - Video Solutions

Problem 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.