See the original problem on HackerRank.
Naive solutions
The naive solution consists in simulating the game: until no elements are left, continuously remove the maximum element and the elements on its right. This might be simplified a bit by performing only a “logical” removal, keeping an index updated to the rightmost element still in the valid range. For example:


Bob “removes” 9
:


It’s clear now that 7
is not in range anymore so Andy picks 6
. Finally, Bob wins by picking 5
.
This solution is quadratic and shown just for completeness:


An improvement consists in speeding up the searching for the maximum element. An idea is to use a support array with the element indexes sorted after the element values. For example:


Then we create this support array:


That contains the indexes of the elements sorted in descending order (9 7 6 5 4
).
We play as before, however we now iterate the maximum elements only once instead of visiting the array all the time.
Bob picks arr[3]
(that is 9
) and updates the last valid index to 3
. The next maximum element is not simply the next one but is also one that is strictly less than 3
. For this reason, arr[4]
(that is 7
) is skipped (indeed, 7
is just after 9
in the original array) and arr[2]
is chosen instead.
The code speaks for itself:


This solution is as expensive as the sorting algorithm (\( O(N \cdot logN) \) in this case) but it works on all test cases.
A better solution is actually more fun and way easier.
Linear solution
To find a better solution we should play the game…the other way around!
Consider again the following sample case:


Imagine we are playing the last move of the game.
We are in this state:


Evidently, we pick 5
and win the game since 4
is dropped as well.
The input array at the last state of the game just contains the very first element and all the next elements that are smaller than it. It can’t be otherwise because any number bigger than 5
have been already picked in previous moves.
Going on with this rewind, we find the state at the second to last move:


Again, 9
and 7
can’t be here at this point because they have been already picked and removed before.
Going back we are at the first state:


Here, 7
is included because smaller than 9
.
The total number of moves is 3
:
 1: Bob removes
9
(and drops7
as well)  2: Andy removes
6
 3: Bob removes
5
(and drops4
as well) and wins
Bob wins. The good news is that we can deduce the winner by checking if the number of moves is even or odd (Bob wins if odd, Andy does otherwise). So, the problem turns into the computation of the number of moves.
The “rewind logic” explained above should be familiar. It consists in iterating the array to keep track of the maximum element. The number of times the maximum is updated corresponds to the number of moves!
Talk is cheap, show me the code:


This solution is smooth and efficient (linear). For completeness, consider that we don’t even need to copy the input values into an array. The proposed solution is online:


To have more fun, which patterns do you see here?
When we calculate a “running thing”, it should smell like a prefix sum. Indeed, here is the trace of an imaginary array containing the maximum elements of 5 4 6 9 7
:


At this point, the number of moves corresponds to the number of unique elements in this array:


Here are a couple of ways to turn this idea into C++ code:


Or using the input array as storage:


We can even apply C++20 ranges (actually, Niebler’s rangev3) and get to this beautiful piece of code:

