Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Climbing the leaderboard challenge

Sharing is caring!

Problem statement
Alice is playing an arcade game and wants to climb to the top of the leaderboard. Can you help her track her ranking as she beats each level? The game uses Dense Ranking, so its leaderboard works like this:

  • The player with the highest score is ranked number 1 on the leaderboard.
  • Players who have equal scores receive the same ranking number, and the next player(s) receive the immediately following ranking number.

For example, four players have the scores 100, 90, 90, and 80. Those players will have ranks 1, 2, 2, and 3, respectively.

When Alice starts playing, there are already n people on the leaderboard. The score of each player i is denoted by s_i. Alice plays for m levels, and we denote her total score after passing each level j as alice_j. After completing each level, Alice wants to know her current rank.

You are given an array, scores, of decreasing leaderboard scores, and another array, alice, of Alice’s cumulative scores for each level of the game. You must print m integers. The j^{th} integer should indicate the current rank of alice after passing the j^{th} level.

Input Format
The first line contains an integer, n, denoting the number of players already on the leaderboard.
The next line contains n space-separated integers describing the respective values of scores_0, scores_1,\dots, scores_{n-1}.
The next line contains an integer, m, denoting the number of levels Alice beats.
The last line contains m space-separated integers describing the respective values of alice_0, alice_1,\dots, alice_{m-1}.

Constraints
1 \le n \le 2\times 10^5
1 \le m \le 2\times 10^5
0 \le scores_i \le 10^9\ for\ 0 \le i \textless n
0 \le alice_j \le 10^9\ for\ 0 \le j \textless m
The existing leaderboard, scores, is in descending order.
Alice’s scores are cumulative, so alice is in ascending order.

Output Format
Print m integers. The j^{th} integer should indicate the rank of alice after passing the j^{th} level.

Sample Input 0

7
100 100 50 40 40 20 10
4
5 25 50 120

Sample Output 0

6
4
2
1

Explanation 0

Alice starts playing with 7 players already on the leaderboard, which looks like this:

After Alice finishes level 0, her score is 5 and her ranking is 6:

After Alice finishes level 1, her score is 25 and her ranking is 4:

After Alice finishes level 2, her score is 50 and her ranking is tied with Caroline at 2:

After Alice finishes level 3, her score is 120 and her ranking is 1:

Solution
The first step we are going to take is determine the largest possible rank. Note that same scores are ranked equally.

int maxRank = 1;
for (int i = 1; i < n; i++) {
    if (score[i] != score[i - 1]) {
        maxRank++;
    }
}

Once we have our largest possible rank, we place Alice in the last position. That is, Alice starts at rank maxRank + 1. Since the scores are already sorted in descending order we can start iterating over them in reverse order starting from the last one while keeping an index of the current score named cursor. We will then keep decreasing Alice's rank (move her one position up in the leaderboard) while her score is greater than the current score. We also keep decreasing our cursor while we have equal consecutive scores. In case of consecutive equal scores we must make sure we decrease Alice's rank only once.

The full code is listed below.

Full code

public class ClimbingTheLeaderboard {
    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt"));
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int[] score = new int[n];
        for (int i = 0; i < n; i++) {
            score[i] = in.nextInt();
        }

        int m = in.nextInt();
        int[] alice = new int[m];
        for (int i = 0; i < m; i++) {
            alice[i] = in.nextInt();
        }

        int maxRank = 1;
        for (int i = 1; i < n; i++) {
            if (score[i] != score[i - 1]) {
                maxRank++;
            }
        }

        int rank = maxRank + 1;
        int cursor = n - 1;
        for (int a = 0; a < m; a++) {
            while (cursor >= 0 && alice[a] >= score[cursor]) {
                boolean flag = false;
                do {
                    cursor--;
                    if (!flag) {
                        rank = Math.max(1, rank - 1);
                        flag = true;
                    }
                } while (cursor > 0 && score[cursor + 1] == score[cursor]);
            }

            System.out.println(rank);
        }
    }
}