Breaking The Records Algorithm

In this article, I'll be describing how I solved the Breaking The Records Challenge on HackerRank using Python 3.

This challenge is part of the Implementation challenges in the Algorithm section on HackerRank.

Problem 🎲

Maria plays college basketball and wants to go pro. Each season she maintains a record of her play. She tabulates the number of times she breaks her season record for most points and least points in a game. Points scored in the first game establish her record for the season, and she begins counting from there.

Example

scores = [12, 24, 10, 24]

Scores are in the same order as the games played. She tabulates her results as follows:

Given the scores for a season, determine the number of times Maria breaks her records for most and least points scored during the season.

Samle Input:

10 5 20 20 4 5 2 25 1

Samle Ouput:

2 4

Explanation

The diagram below depicts the number of times Maria broke her best and worst records throughout the season:

She broke her best record twice (after games 2 and 7) and her worst record four times (after games 1, 4, 6, and 8), so we print 2 4 as our answer. Note that she did not break her record for best score during game 3, as her score during that game was not strictly greater than her best record at the time.

I'll get right into the algorithm. Please feel free to read the full question on HackerRank.

Solution 🔎

In plain English, this problem requires us to determine how many times Maria breaks a record after setting it, depending on if it was her highest or lowest record yet.

So how do we think about this problem? 🤔🤔

Step 1️⃣: Loop through all the games. ⚽

1. We'll first start by looping through all the games Maria plays, and then apply various conditional logic to check if the current game score is the highest or lowest score.
2. To do this, we'll first need to create variables to store the following things:
3. HS, an array of integers to store the current highest score after each game. This initially contains only the score of the first game by default.
4. LS, an array of integers to store the current lowest score after each game. This also initially contains only the score of the first game by default.
5. curr_HS, used to store the current highest score after each game.
6. curr_LS, used to store the current lowest score after each game.

def breakingRecords(scores):
    # Write your code here

    curr_HS = scores[0]
    curr_LS = scores[0]
    HS = [curr_HS]
    LS = [curr_LS]

    for i in range(1, len(scores)):
    ...

Step 2️⃣: Developing the record checking logic.

We'll check for three different conditions to determine whether a current score is a highest or lowest score. Here's how we'll do it.

1. For any given game, we'll check if the current score, score[i] is greater than the current highest score, curr_HS.
2. if it is, we'll add this current score to the highest scores array HS, and return the lowest scores array, LS array with the current lowest score added to it.
3. Then we'll do the reverse if the current score, score[i] is less than the current lowest score, curr_LS.
4. if it is, we'll add this current score to the lowest scores array LS, and return the highest scores array HS with the current highest score added to it.
5. Finally, if the current score, score[i] is neither greater nor less than the current highest score, curr_HS or current lowest score, curr_LS, we'll simply return the highest scores array HS and the lowest scores array, LS array with the current highest score and lowest score added to it respectively.

   Remeber the aim of these conditions isn't simply to create arrays with the highest scores and lowest scores but to also determine the current highest score and lowest score.

6. To determine these scores after each iteration we'll set the current highest score to be the largest number in the highest scores array, and equally set the current lowest score to the smallest number in the lowest scores array too.

        if scores[i] > curr_HS:
            HS.append(scores[i])
            LS.append(curr_LS)
        elif scores[i] < curr_LS:
            LS.append(scores[i])
            HS.append(curr_HS)
        else:
            HS.append(curr_HS)
            LS.append(curr_LS)

        curr_HS = max(HS)
        curr_LS = min(LS)

Now we have successfully created these arrays which will help us count how many times Maria breaks a record after setting it, depending on if it was her highest or lowest record yet.

This brings us to the final step. ⚙️⚙️

Step 3️⃣: Count the number of times the scores are increasing and decreasing. 🤔

This was tricky, but luckily as it is with programming, someone else had asked this question before.😏

1. The idea here is to loop through the two arrays we created and check if a score for a given game n in one array is larger or smaller than the score in a previous game n-1.

   But here's the trick, we have to loop between, say, the highest scores array and the highest scores array starting with scores after the first game.

2. This way, we can easily compare scores side by side to determine if the score at game n is larger or smaller than that of game n-1.🤓🤓

3. Finally, we return the number of times this happens by calling sum(). Thereafter, returning this number in a new array containing HH and LL for the highest scores and lowest scores arrays respectively.

    HH = sum(b > a for a, b in zip(HS, HS[1:]))   
    LL = sum(b < a for a, b in zip(LS, LS[1:])) 

    return [HH, LL]

Full code:

def breakingRecords(scores):
    # Write your code here

    curr_HS = scores[0]
    curr_LS = scores[0]
    HS = [curr_HS]
    LS = [curr_LS]

    for i in range(1, len(scores)):

        if scores[i] > curr_HS:
            HS.append(scores[i])
            LS.append(curr_LS)
        elif scores[i] < curr_LS:
            LS.append(scores[i])
            HS.append(curr_HS)
        else:
            HS.append(curr_HS)
            LS.append(curr_LS)

        curr_HS = max(HS)
        curr_LS = min(LS)


    HH = sum(b > a for a, b in zip(HS, HS[1:]))   
    LL = sum(b < a for a, b in zip(LS, LS[1:])) 

    return [HH, LL]



breakingRecords([3, 4, 21, 36, 10, 28, 35, 5, 24, 42])
>> 4 0

Explanation

She broke her best record four times (after games 1, 2, 3, and 9) and her worst record zero times (no score during the season was lower than the one she earned during her first game), so we print 4 0 as our answer.

Hope this helps with understanding this challenge. Happy Coding!👨🏽‍💻