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.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Implementation
  4. Climbing the Leaderboard
  5. Discussions

Climbing the Leaderboard

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 1812 Discussions, By:

votes

Please Login in order to post a comment

  • Tomheza
    5 years ago+ 110 comments

    I have one tip for you guys: go from the lowest to highest and start at index that you checked last, last time that way you wont need to go through entire array every time!

    519|
    Permalink
    View more Comments..
  • Kanahaiya
    3 years ago+ 14 comments

    Hello friends,

    climbing the leaderboard can be optimized by applying binary search

    If interested to know more about the generic algorithm in details-

    click here for the video explanation of generic algorithm with complexity analysis.

    or you can click on the image too to follow youtube tutorial.

    Here is the working solution:-

    source code :

    static int[] climbingLeaderboard(int[] scores, int[] alice) {
    	int n = scores.length;
    	int m = alice.length;
    
    	int res[] = new int[m];
    	int[] rank = new int[n];
    
    	rank[0] = 1;
    
    	for (int i = 1; i < n; i++) {
    		if (scores[i] == scores[i - 1]) {
    			rank[i] = rank[i - 1];
    		} else {
    			rank[i] = rank[i - 1] + 1;
    		}
    	}
    
    	for (int i = 0; i < m; i++) {
    		int aliceScore = alice[i];
    		if (aliceScore > scores[0]) {
    			res[i] = 1;
    		} else if (aliceScore < scores[n - 1]) {
    			res[i] = rank[n - 1] + 1;
    		} else {
    			int index = binarySearch(scores, aliceScore);
    			res[i] = rank[index];
    
    		}
    	}
    	return res;
    
    }
    
    private static int binarySearch(int[] a, int key) {
    
    	int lo = 0;
    	int hi = a.length - 1;
    
    	while (lo <= hi) {
    		int mid = lo + (hi - lo) / 2;
    		if (a[mid] == key) {
    			return mid;
    		} else if (a[mid] < key && key < a[mid - 1]) {
    			return mid;
    		} else if (a[mid] > key && key >= a[mid + 1]) {
    			return mid + 1;
    		} else if (a[mid] < key) {
    			hi = mid - 1;
    		} else if (a[mid] > key) {
    			lo = mid + 1;
    		}
    	}
    	return -1;
    }
    

    Would really appreciate your feedback like, dislike , comment etc. on my video.

    Do not forget to upvote, if you find it useful.

    130|
    Permalink
    View more Comments..
  • quachtridat
    5 years ago+ 26 comments

    My solution was to use stack and to store only distinct numbers.

    #include <stack>
    #include <iostream>
    using namespace std;
    
    int main(){
      unsigned long n, m, i, tmp;
      cin >> n;
      stack<unsigned long> scores;
      for (i = 0; i < n; ++i) {
        cin >> tmp;
        if (scores.empty() || scores.top() != tmp) scores.push(tmp);
      }
      cin >> m;
      for (i = 0; i < m; ++i) {
        cin >> tmp;
        while (!scores.empty() && tmp >= scores.top()) scores.pop();
        cout << (scores.size() + 1) << endl;
      }
      return 0;
    }
    

    One more good solution without using stack is to store only distinct numbers like above, then we can use binary search to find out the rank, as nelson_matos brought in at https://www.hackerrank.com/challenges/climbing-the-leaderboard/forum/comments/271253.

    117|
    Permalink
    View more Comments..
  • albiewalbie
    5 years ago+ 22 comments

    Python 2

    n = int(raw_input().strip())
    scores = map(int,raw_input().strip().split(' '))
    m = int(raw_input().strip())
    alice = map(int,raw_input().strip().split(' '))
    
    leaderboard = sorted(set(scores), reverse = True)
    l = len(leaderboard)
    
    for a in alice:
        while (l > 0) and (a >= leaderboard[l-1]):
            l -= 1
        print l+1
    
    82|
    Permalink
    View more Comments..
  • nelson_matos
    5 years ago+ 6 comments

    A good way to solve the problem is to store distinct values of the scores with O(N) complexity. For example, Test Case scores are: 100 100 50 40 40 20 10

    You only need to store: 100 50 40 20 10

    Then use a simple binary search catered to a descending list which returns the corresponding index.

    32|
    Permalink
    View more Comments..
Load more conversations

Need Help?


View editorial
View top submissions
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature