# Leader-Board Problem in Data Structure

\$\$/\$\$

Now that a lot about sorting algorithms has been discussed, you must try to solve the second query of the leaderboard problem discussed at the beginning of the module. In the next video, industry expert Ankit Maheshwari will discuss the approach one needs to take to crack that problem. Let’s see what he has to say before we move on to the code.

\$\$/\$\$

## Video Recap

• One way to achieve this is by doing passes on the array and picking the next highest every time, which takes order (N*K) time.

• Alternatively, the list of players can be sorted by their scores using an order and login-based sorting algorithm and then return the top K players from the sorted list of players.

• For large values of k, the order N(log(N)) method is better than the order (N*K) method.

• Merge sort and Quicksort are two sorting algorithms with order (N) login time complexity, but Quicksort has a worst-case scenario of order (N) square time complexity.

• The standard library function of the collections class in Java uses an enhanced version of merge sort and takes in two arguments: the list to be sorted and a comparator object that provides rules for sorting.

• The comparator object in this case compares the score of the players and uses the timestamp as a tiebreaker if the scores are equal.

• The pseudo code for the compare function is to calculate the difference between the scores of the two players, and if the difference is not zero, return the difference. If the difference is zero, compare the timestamps and return the result.

• Sorting the list is just calling a single library method after creating the comparator with the right compare function.

Great! You saw that you can use the ‘Collections.sort’ function to implement merge sort in our program. This program takes a comparator as an input, which basically sets the rules for this sorting. In case of a tie, you shall use timestamps of the players to assign them to the ranks. Let’s see the Java code for this in the video below.

\$\$/\$\$

As you saw in the video, Ankit used timestamps in the occurrence of a tie. Also, if the email ID does not exist in the list, the program prints a message saying that the email ID does not exist.