Problem Brief

Rank Songs by Popularity

INTERNOA

As part of enhancing a music streaming platform's user experience, implement a feature that ranks songs by their popularity. Given n users and m songs, each user i has a preference list, pref[i], which is a permutation of numbers 0 to m-1, indicating the user's preference for a song. If a < b, the user prefers song pref[i][a] over song pref[i][b].

To rank the songs, use the following approach. Song x is said to beat song y if x is preferred over y by more than half of the users or if exactly half of the users prefer x over y, and x has a smaller id. Song x is considered more popular than song y if x beats more songs than y. If x and y beat the same number of songs, select the song with a lower id.

1Example 1

Input

n = 3, m = 3, pref = [[0, 1, 2], [0, 2, 1], [1, 2, 0]]

Output

[0, 1, 2]

Explanation

User Song Preference
0 Song 0 > Song 1 > Song 2
1 Song 0 > Song 2 > Song 1
2 Song 1 > Song 2 > Song 0

Comparisons:
Song Pair Users who prefer
Song 0 > Song 1 0, 1
Song 0 > Song 2 0, 1
Song 1 > Song 2 0, 2

It is established that Song 0 > Song 1 > Song 2. Hence the answer is [0, 1, 2].

Constraints

Limits and guarantees your solution can rely on.

🐭