0205MediumArrayBinary SearchGreedySliding WindowSortingPrefix Sum

Plates at One Thickness

Tracked in this browser only

Trains the technique from

LeetCode 1838Frequency of the Most Frequent Element

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 plating shop builds press plates up to size with a spray gun. plates gives the current thickness of each plate in microns, in no particular order, and coating is how many microns of spray are left in the tank altogether.

One micron of spray raises one plate by one micron and draws one micron from the tank. You may spray any plate as often as you like, in any order, but spray can never be stripped back off, so no plate ever gets thinner. You are not obliged to empty the tank.

The press only accepts a batch of plates that all measure exactly the same. Return the largest number of plates that can be brought to one common thickness.

Examples

Example 1

Input: plates = [9, 4, 8, 8, 6], coating = 4
Output: 3

Spray 2 microns onto the plate at 6 to bring it to 8. Together with the two plates already at 8 that makes three plates measuring 8, with 2 microns still in the tank.

Example 2

Input: plates = [2, 4], coating = 2
Output: 2

Both microns go on the plate at 2, lifting it to 4 so that both plates measure 4.

Example 3

Input: plates = [7, 7, 7, 7], coating = 1
Output: 4

All four plates already measure 7, so the batch is complete without spraying anything.

Example 4

Input: plates = [1, 2, 3, 4, 100], coating = 2
Output: 2

Spraying 2 microns onto the plate at 2 takes it to 4, which matches the plate already at 4, giving two plates at the same measure.

Constraints

1 <= plates.length <= 10^5
1 <= plates[i] <= 10^5
1 <= coating <= 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 max_matched_plates(plates: list[int], coating: int) -> int:

Java

public int maxMatchedPlates(int[] plates, int coating)

The intended approach

Time O(n log n)Space O(n)

Sort the thicknesses. Since spray only adds material, a batch is settled by its thickest member, and for a fixed batch size the cheapest choice is a run of plates that sit next to each other in sorted order, lifted to the value at the right end of that run. Slide a window across the sorted list carrying its running sum: the spray needed is the right-hand value times the window width minus that sum. Whenever the figure passes `coating`, drop plates off the left end until it fits again, and track the widest window the pass ever holds.

Pythonentry point: max_matched_plates

def max_matched_plates(plates, coating):
    # Time O(n log n) for the sort plus one linear window pass.
    # Space O(n) for the sorted copy of the thicknesses.
    ordered = sorted(plates)
    window_sum = 0
    left = 0
    best = 1
    for right, value in enumerate(ordered):
        window_sum += value
        while value * (right - left + 1) - window_sum > coating:
            window_sum -= ordered[left]
            left += 1
        width = right - left + 1
        if width > best:
            best = width
    return best

The obvious version

Sort, then treat every plate in turn as the target thickness and walk downward from it adding up the spray each earlier plate needs, stopping when the tank runs dry. Recomputes the cost from scratch per candidate, O(n^2).

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_max_matched_plates(plates, coating):
    ordered = sorted(plates)
    best = 1
    for i in range(len(ordered)):
        target = ordered[i]
        spent = 0
        count = 0
        j = i
        while j >= 0:
            spent += target - ordered[j]
            if spent > coating:
                break
            count += 1
            j -= 1
        if count > best:
            best = count
    return best

How this problem was checked

Reference solution executed against 18 test cases — 18 passed
4 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