Funcia
Lv.1binary-searchhashsorting

Score Ranks

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

scores holds the students' exam scores. A student's rank is one plus the number of students with a strictly higher score, so tied students share a rank and the next rank skips accordingly. Return every student's rank in the order of scores.

Examples

scoresresult
[90, 100, 90, 80][2, 1, 2, 4]
[50][1]
[70, 70, 70][1, 1, 1]

Example 1 — the two 90s share rank 2, and three students beat 80, so it is rank 4 (there is no rank 3).

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(scores: int[]) → int[]

Constraints

  • 1≤1 \le scores.length ≤200,000\le 200{,}000
  • 0≤0 \le scores[i] ≤109\le 10^9

Expected complexity

Time
O(N log N)
Space
O(N)

Examples

scoresExpected
[90,100,90,80][2,1,2,4]
[50][1]
[70,70,70][1,1,1]

Hint

Hint

In the scores sorted in descending order, the first position (0-based) of a score equals the number of higher scores; store "first position + 1" per score in a hash map. Alternatively, sort ascending and use an upper-bound binary search to count the larger values. Comparing every student with every other is O(N2)O(N^2) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251570 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4010verdict only
performance603verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.