Show problems as
Classic problem #3948HardArrayHash TableGreedyQueue

Lexicographically Maximum MEX Array

Real-world version: Largest Group Gap Report
Tracked in this browser only
Read Lexicographically Maximum MEX Array on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A conveyor carries bins in a fixed order. Bin i holds a token stamped with the whole number nums[i].

The MEX of a collection of tokens is the least non-negative integer that no token in the collection carries. So a collection with no 0 has MEX 0, and a collection holding 0 and 1 but no 2 has MEX 2.

You cut the conveyor into consecutive groups: every bin lands in exactly one group, no group is empty, and the groups keep conveyor order. The report of a cut is the list of the MEX values of its groups, in the same order as the groups.

Return the largest report under this comparison: compare two reports at the first position where they differ, and the one with the bigger value there is larger; if neither differs anywhere and one is shorter, the longer report is larger. Any number of groups from one up to nums.length is allowed.

Examples

Example 1

Input
nums = [5,0,3,1,2,0]
Output
[4,1]

Cutting after the fifth bin gives the groups `[5,0,3,1,2]` and `[0]`. The first group misses 4 and carries everything below it, so its MEX is 4; the second group carries 0 and misses 1, so its MEX is 1.

Example 2

Input
nums = [0,2,1,0,0]
Output
[3,1,1]

The groups are `[0,2,1]`, `[0]` and `[0]`, with MEX values 3, 1 and 1. Every bin sits in exactly one group and the order is kept.

Example 3

Input
nums = [7,7]
Output
[0,0]

No bin carries 0, so any group at all has MEX 0. Splitting into two single-bin groups gives a report of two zeros, which beats the shorter report `[0]` from a single group.

Constraints

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^5

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def maximum_m_e_x(nums: list[int]) -> list[int]:
Java
public int[] maximumMEX(int[] nums)

More on the same topics