0343HardArrayHash TableGreedyQueue

Largest Group Gap Report

Tracked in this browser only

Trains the technique from

LeetCode 3948Lexicographically Maximum MEX Array

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def maximum_m_e_x(nums: list[int]) -> list[int]:

Java

public int[] maximumMEX(int[] nums)

The intended approach

Time O(n)Space O(n) for the suffix table and the returned report

Because a group only gains tokens as it grows, its MEX never falls, so the best value the next group can report is the MEX of everything still on the conveyor. Precompute the MEX of every suffix in one right-to-left sweep, then walk forward closing each group as soon as it reaches its suffix target and starting the next group from the following bin.

Pythonentry point: maximum_m_e_x

def maximum_m_e_x(nums):
    n = len(nums)
    # suffix[i] is the MEX of nums[i:].  Sweeping right to left, the running MEX
    # only ever climbs, so the whole table costs one pass.
    suffix = [0] * (n + 1)
    seen = [False] * (n + 2)
    mex = 0
    for i in range(n - 1, -1, -1):
        v = nums[i]
        if v <= n:
            seen[v] = True
        while seen[mex]:
            mex += 1
        suffix[i] = mex
    out = []
    i = 0
    while i < n:
        target = suffix[i]
        have = [False] * (target + 2)
        reached = 0
        j = i
        while True:
            v = nums[j]
            if v <= target:
                have[v] = True
            while reached < target and have[reached]:
                reached += 1
            j += 1
            if reached >= target:
                break
        out.append(target)
        i = j
    return out
    # Time O(n): the suffix sweep is one pass and every bin is read once more
    # while its group is being closed.  Space O(n) for the suffix table plus the
    # returned report.

The obvious version

For each starting bin, try every group end, keep the largest MEX any of them reaches, then re-scan from the start to find the earliest end that reaches it. Rebuilds a set from scratch every time, so it is quadratic.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_group_mex_report(nums):
    def mex_of(values):
        pool = set(values)
        m = 0
        while m in pool:
            m += 1
        return m

    n = len(nums)
    out = []
    i = 0
    while i < n:
        best = 0
        for j in range(i + 1, n + 1):
            m = mex_of(nums[i:j])
            if m > best:
                best = m
        j = i + 1
        while mex_of(nums[i:j]) != best:
            j += 1
        out.append(best)
        i = j
    return out

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in