Show problems as
Classic problem #274MediumArraySortingCounting Sort

H-Index

Real-world version: Bakery Staple Score
Tracked in this browser only
Read H-Index on LeetCode(opens in a new tab)

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

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

Python
def staple_score(orders: list[int]) -> int:
Java
public int stapleScore(int[] orders)

More on the same topics