Loading page…
Practice problem · medium
A video app wants one number that rates a creator by both volume and reach. It uses the h-index. A creator has h-index h when at least h of their videos have h views or more each.
You get the view counts of one creator's videos. Find the largest h that holds.
Write h_index(views).
views[i] is the number of views of video i.h such that at least h videos have views[i] >= h.h of 1 or more holds.Input: views = [3, 0, 6, 1, 5]
Output: 3Sort the views from largest to smallest, then give each video a rank from 1.
| Rank | Views, largest first | Views ≥ rank? |
|---|---|---|
| 1 | 6 | yes |
| 2 | 5 | yes |
| 3 | 3 | yes |
| 4 | 1 | no |
| 5 | 0 | no |
Rank 3 is the last rank whose video has at least 3 views, so the h-index is 3.
Input: views = [100, 100]
Output: 2Both videos have at least 2 views, so h = 2. The index can never be more than the number of videos.
Input: views = [0, 0, 0]
Output: 0No video has even 1 view, so there is no h of 1 or more.
0 ≤ views.length ≤ 100,000 (videos)0 ≤ views[i] ≤ 1,000,000Trying each h from n downwards and counting the videos with at least h views costs about n × n, which is 10^10 at n = 100,000. Sorting once costs about n log n, and one pass after it costs n.
h_index · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.