Climbing the Leaderboard
Climbing the Leaderboard
+ 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!
+ 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.
+ 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.
+ 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
+ 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.
Sort 1812 Discussions, By:
Please Login in order to post a comment