Beating AlgoExpert: Min Rewards

I love a good algorithm, it wakes me up in the morning better than the strongest cup of coffee. So I spend a lot of time on AlgoExpert, LeetCode, and HackerRank. What gets me really excited, is when I can build a better algorithm than the experts, especially since I only just finished my software engineering bootcamp. This is the first of a series I plan to write about times I have built better solutions (in my opinion) than AlgoExpert. If you disagree with my solutions or find problems, please comment. I love being proven wrong, it’s a fantastic way to learn.

The Problem

Today’s problem is titled Min Rewards. A teacher has an array of student scores, and the teacher must purchase rewards to give to the students based on their score. The amount of rewards must follow 2 criteria:

1. Each student must have at least one reward.
2. The higher ranked student of two adjacent students must have more rewards than the other.

The goal is to find the minimum number of rewards to purchase. You can also find the problem on LeetCode but there is a slight difference between the two in that AlgoExpert’s prompt uses only distinct integers in the input array while LeetCode’s prompt allows for duplicate scores. I will cover how to adapt to the LeetCode version in the end.

To clarify here is a sample problem:

Their Solution

There are three solutions provided but we are gonna jump to their most efficient one. In this solution they set up a rewards array with the same length as the scores input array and initialized to 1 for each index.

They then go through the scores array starting at index 1 and and increase the corresponding index in the rewards array by one if the score to the left is lower.

They then go through the array backwards starting at one less than the last index and increase the corresponding index in the rewards array by one if the score to the right is lower.

At the end they sum up the rewards array with a reduce function and return it. Their full solution is below:

Breaking down the patterns

This solution is very effective since they are achieving a big O run time of O(n) but they are also using a big O space complexity of O(n) and I will show you how to beat it with a space complexity of O(1).

Iterating through the array and comparing to the previous values, we will come across 2 distinct situations that we must handle. The previous score was higher, or the previous score was lower.

If the previous score was lower, we increase the last rewards by one and move on. This is the easy case and we can see it play out in the middle of our example.

If the previous score was higher, it is a little trickier. We want to set the rewards for the lower score to one, then increase every previous score in a series of decreasing scores enough to maintain rule 2 of the criteria. What this means is that every one before who has a higher score would get one more reward. You can see this below.

If we consider the first 4 scores of the input array, we can start off with giving first student one reward. Then we see that the second student has a lower score, so their reward is now one and the first student is now getting two rewards. This pattern continues and we can utilize it so that every time we add a student to a set of continuously decreasing scores, we increase the total rewards by the number of students in that series.

Now there is one caveat to this that we need to be aware of, let’s move towards the end of the the solution. Where we have scores of 9 and 5 and get another series of two decreases in a row.

Now in this instance the score of 9 has already been given a reward of 5 and it can’t go any lower because of the numbers preceding it. But we also don’t want to increase because the score of 5 was was added to the series of decreasing scores. So what we need to do is track the previous max and check to see that is greater than or equal to the number we have in our decreasing series.

We can keep adding decreasing scores, and once that series becomes large enough the student with score of 9 will need to receive more than 5 rewards. Let’s put this to code to make it more clear.

Throwing down the gauntlet!

I will walk you through my solution, but if you want, just can skip down to the actual code to reverse engineer it your self. It may be easier to understand that way.

We are going to track 4 variables, all of which have been initialized to 1.

studentsInDecrease: the number of students in a decreasing series

previousMaxAwards: the previous maximum awards in a series

previousAwards: the last number of awards given

totalAwards: our running total awards that we need

Next we will iterate through the scores array starting at index 1 and compare it to the previous score. Remember there are two outcomes to this comparison, only less or more. Duplicates do not exist unless you tackle to Leetcode version.

If the score is less than the previous score, we increase the number students in our decrease series. Now that that variable is updated we can then increase the total awards by that variable. Lastly we will check if previousMaxAwards ≥ studentsInDecrease, this is the caveat we discussed in the previous section. If previousMaxAwards is greater than or equal to studentsInDecrease, we don’t need to increase the number of awards the first student in the decrease series. To handle that, we decrease total awards by one.

If the score is greater, we can reset studentsInDecrease to 1, increase previousAwards by one set previousMaxAwards to previousAwards and increase totalAwards by previousMaxAwards.

At the end return totalAwards, solution below:

As you can see, we get an O(n) in time complexity, same as AlgoExpert, but are also able to achieve a O(1) in space complexity, which in my mind is an improvement over their solution.

Adjusting for LeetCode’s version

My version currently stands as beating 100% of all submissions by LeetCode’s measurements, but perhaps I just got lucky with the server speeds. I promise I haven’t let it go to my head.

As mentioned above, LeetCode’s version allows for duplicate scores (also rewards are candies, a great improvement in my mind) so there is a third situation that can occur in our initial comparison being that two adjacent scores are the same. In this case we reset all variables except total rewards to 1 and increase total rewards by 1.

Please leave any thoughts or comments. Happy coding!