0305MediumArraySortingCounting Sort

Bakery Staple Score

Tracked in this browser only

Trains the technique from

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 bakery keeps one entry per cake design on its menu. orders[i] is how many times design i was ordered over the past season.

The owner grades the whole menu with a single number called the staple score: the largest value s for which the menu contains s or more designs that were each ordered s or more times. A menu where nothing was ever ordered scores 0.

Given orders, return the staple score. The entries arrive in menu order, which has nothing to do with popularity.

Examples

Example 1

Input: orders = [7, 1, 4, 4, 2]
Output: 3

Designs with 7, 4 and 4 orders give three designs at three or more orders each, so 3 works. A score of 4 would need four designs at four or more orders, and only three designs reach four.

Example 2

Input: orders = [12, 12, 12, 12]
Output: 4

All four designs were ordered at least four times, so 4 works. The menu only has four designs, so no larger score is possible.

Example 3

Input: orders = [6, 6, 2, 2, 2, 2]
Output: 2

Every one of the six designs was ordered at least twice, so 2 works. A score of 3 would need three designs at three or more orders, and only the two designs with 6 orders qualify.

Example 4

Input: orders = [5]
Output: 1

The single design was ordered five times, which is at least one, so 1 works. A one-design menu can never support a score of 2.

Constraints

n == orders.length
1 <= n <= 5000
0 <= orders[i] <= 1000

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 staple_score(orders: list[int]) -> int:

Java

public int stapleScore(int[] orders)

The intended approach

Time O(n)Space O(n) for the bucket array

The score can never exceed the number of designs, so every order count above `n` is as good as exactly `n`. Bucket the counts into an array of length `n + 1`, clamping each count at `n`, then sweep `s` from `n` down to 0 while accumulating how many designs sit at `s` or more orders. The first `s` whose running total reaches `s` is the answer.

Pythonentry point: staple_score

def staple_score(orders):
    # O(n) time: one pass to bucket, one downward sweep over n + 1 buckets.
    # O(n) space for the bucket array.
    n = len(orders)
    buckets = [0] * (n + 1)
    for v in orders:
        buckets[v if v < n else n] += 1
    seen = 0
    for s in range(n, 0, -1):
        seen += buckets[s]
        if seen >= s:
            return s
    return 0

The obvious version

Try every candidate score from n downwards and, for each, recount from scratch how many designs meet that many orders.

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_staple_score(orders):
    n = len(orders)
    for s in range(n, 0, -1):
        hits = 0
        for v in orders:
            if v >= s:
                hits += 1
        if hits >= s:
            return s
    return 0

How this problem was checked

Reference solution executed against 12 test cases — 12 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