We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Implementation
  4. Climbing the Leaderboard
  5. Discussions

Climbing the Leaderboard

  • chaudhary__jr
     + 2 comments

    Java Solution with runtime complexity O(# of distinct scores of students + # of tests given by alice)

    I iterate throught the distinct scores and since i am using stack the top is least rank and also the alice's score are in in increasing order which means if i have calculated the rank for first score to be 4 out of 6 the rest of the ranks will be less then 4 and i used this fact to limit the complexity to size of array. 

    import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] scores = new int[n];
        for(int scores_i=0; scores_i < n; scores_i++){
            scores[scores_i] = in.nextInt();
        }
        int m = in.nextInt();
        int[] alice = new int[m];
        for(int alice_i=0; alice_i < m; alice_i++){
            alice[alice_i] = in.nextInt();
        }
        // your code goes here
        Stack<Integer> st=new Stack<Integer>();
        int rank=0;
        st.push(scores[0]);
        for(int i=1;i<scores.length;i++)
        {
            if(scores[i]!=st.peek())
                st.push(scores[i]);
        }
        //Pushed distinct elements onto the stack.
        //Then i set the rank to the size of stack+1, and iterate through the scores and if alice's score is greater or equal to the top i pop and decrement the rank.   
        rank=st.size()+1;
        for(int j=0;j<alice.length;j++)
        {
            
            while((!st.empty())&&(alice[j] >= st.peek()))
            {
                st.pop();
                rank--;
            }
            System.out.println(rank);
        }
    }
}

    Please correct me if my complexity is something else.