Find the Largest Rating Threshold Supported by K Instances

Given an array of integer instance ratings, return the largest integer k such that at least k instances have ratings greater than or equal to k.

Input and Output

• Input: an array of integer ratings, one value per instance.
• Output: one integer, the maximum qualifying k. Return 0 when no positive k qualifies.
• k cannot exceed the number of instances. A rating equal to k meets the threshold.
• For this practice version, an empty array has answer 0.

Example 1

ratings = [3, 0, 6, 1, 5]
answer = 3

Three ratings are at least 3: 3, 6, and 5.

Example 2

ratings = [0, 0]
answer = 0

Largest Rating Threshold With Enough Instances

Constraints

• ratings is a finite array of integers and may be empty.
• No rating-magnitude or array-size bound is supplied.
• Return the largest k between 0 and the number of instances with at least k ratings greater than or equal to k.

Hints

1. A threshold cannot exceed the number of instances.
2. A rating equal to the threshold counts toward it.

Approach

If there are n ratings, no valid threshold exceeds n. Count how many ratings fall at each positive threshold from 1 through n, placing every rating at least n in the n bucket; nonpositive ratings contribute to none. Scan thresholds from n down to 1 while accumulating the number of ratings at least that threshold. The first threshold whose accumulated count is at least the threshold is the maximum qualifying k. Equality is included by the bucket count. Empty input has no positive threshold.

• Time complexity: O(n), where n is the number of ratings.
• Space complexity: O(n) for threshold buckets.