USACO 2025 Making Mexes: Frequency Counting and One-Pass Sweep

Many USACO Bronze problems look like story problems at first, but the winning move is often to translate the story into a small amount of state. Making Mexes is a good example because the problem can feel like many separate cases, but the core idea is a clean frequency-counting sweep.

The idea without memorizing the solution

The MEX of an array is the smallest non-negative integer that does not appear. If we want the array to have MEX i, two things must be true:

• Every value from 0 through i - 1 must appear at least once.
• The value i must not appear.

That gives students a concrete checklist. For each possible MEX, count how many smaller values are missing and how many copies of the MEX value must be removed.

Small dry run

Suppose the current array is:

[0, 0, 2]

The useful frequency counts are:

Value	Count
0	2
1	0
2	1

Now test each desired MEX:

Desired MEX	Missing smaller values	Copies of MEX to remove	Minimum changes
0	0	2	2
1	0	0	0
2	1	1	1
3	1	0	1

The key observation is that the answer for MEX i is controlled by the larger of two requirements:

answer[i] = max(count[i], missingSmallerValues)

Copies of i must be changed because i cannot remain in the array. Missing smaller values must be created. The same changed positions can sometimes help with both goals, which is why the maximum is enough.

Why a sweep works

When moving from desired MEX i to desired MEX i + 1, only one new smaller value becomes required: i. If i was absent, the missing count increases by one. If it was present, nothing new is missing.

missing = 0
for i from 0 to N:
    answer = max(count[i], missing)
    print(answer)
    if count[i] == 0:
        missing = missing + 1

Java implementation shape

A Bronze-friendly Java version usually has three blocks: read values, build counts, sweep possible MEX values.

int[] count = new int[n + 2];
for (int value : values)
{
    if (value <= n)
    {
        count[value]++;
    }
}

int missing = 0;
for (int mex = 0; mex <= n; mex++)
{
    int changes = Math.max(count[mex], missing);
    System.out.println(changes);

    if (count[mex] == 0)
    {
        missing++;
    }
}

Common mistakes

• Counting values larger than N too carefully: for MEX values from 0 to N, larger values do not need their own frequency bucket.
• Using addition instead of max: the operations can overlap because changing a forbidden MEX value can create a missing smaller value.
• Updating missing too early: print the answer for MEX i before making i required for the next step.
• Forgetting MEX N: an array of length N can have MEX N if every value 0..N-1 appears.

Practice prompt

Try the same sweep on [1, 1, 3, 0]. Build the frequency table, list answers for MEX 0 through 4, and explain exactly when missing increases.