Climbing the Leaderboard — Medium HackerRank Exercise

Photo by Sorin Gheorghita on Unsplash

LinkedIn Twitter Original Blog Github HackerRank

Alice is playing an arcade game and wants to climb to the top of the leaderboard and wants to track her ranking. 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, the four players on the leaderboard have high scores of 100, 90, 90, and 80. Those players will have ranks 1, 2, 2, and 3, respectively. If Alice’s scores are 70, 80, and 105, her rankings after each game are 4, 3, and 1.

Function Description

Complete the climbingLeaderboard function in the editor below. It should return an integer array where each element res[j] represents Alice’s rank after the jth game.

climbingLeaderboard has the following parameter(s):

  • scores: an array of integers that represent leaderboard scores
  • Alice: an array of integers that represent Alice’s scores

So if Alice will get [5, 25, 50, 120], then these scores will be with the next ranks [6, 4, 2, 1].

About Binary Search

Medium exercises always have some background. This exercise can be solved in a non-optimized way, but HackerRank won’t give you 100%. It will be a problem with complexity.

The answer is Binary Search. I will give you some markers which can help you to decide if Binary Search can help you in any exercise.

It can be a Binary Search If:

  • You have a sorted sequence (from min to max or max to min)
  • You need to find a place of some value in sequence or place of closest value in this sequence (search exercise)

This exercise can be solved with a linear algorithm with O(n) complexity. It is easy to understand what it is. Let say that 1 iteration gets 1 second. If your sequence has 1 million items it will have 1 million iterations and it will take 1 million seconds. But binary search gives us a log2(n) complexity, and this exercise can be solved with only 19,932 iterations instead of 1 million. And it is so cool for the complexity.

Binary Search is simple for understanding. If you have a sorted array from min to the max for example — [1, 2, 3, 4, 5, 6, 7, 8], and you need to find the index of number 7 then you can easily use binary search for this. At first, you need to find the mid-index of this sequence.

mid-index = array.count / 2 = 8 / 2 = 4.

Now we can check if the number on index 4 is greater or lower then our searched value. Okay, 7 is greater than 5, it means that we don’t need to check numbers from 0 to 4 indexes. We know that all numbers which stand left from number 5 are lower than 5. And it is a method of binary search. We need to get a mid-index of sequence and search only in the needed part of the sequence.

Solving

With an understanding of binary search, we can easily find the closest values of each Alice’s score with a small number of iterations. At first, we need to create a table of places that depend on the input table. After that, find the closest value to each score of Alice. And that’s all. With closest values, we can define the place of Alice with each of the input scores.

My Social Media

LinkedIn Twitter Original Blog Github HackerRank

--

--

--

iOS Software Developer

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Swift UIView Cheat Sheet II — Visual Appearance

The No Code Movement

Deployment of Mule application to Cloudhub using connected app

Avoid headache from creating diagrams — use PlantUML

How To Study Better As A Self-Taught Developer

Selenium 4.0 alpha released — What Test Automation Engineers can expect!

Master CSS Flexbox

The Main Factors to Consider Before Choosing a VPS Plan

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Almost Engineer

Almost Engineer

iOS Software Developer

More from Medium

[LeetCode] 1614. Maximum Nesting Depth of the Parentheses (Swift)

How we made our emailing service resilient — Part 1

Dynamic Linker Not Working in Big Sur

Cisco IOS Ultimate Guide