HackerRank Java 1D Array (Part 2)

Don't be misled by its puzzling name, this fun little HackerRank problem has its main interest not in its implementation language nor in the use of the array data structure, but in the algorithm you apply to solve it.

There is a one dimensional board. Each cell in it could be set to zero (meaning free) or one. At startup the pawn is placed on the first cell to the left, and its job is going out to the right. It could be moved only moving forward by 1 or 'leap' positions, or backward just by one, but only to free (set to zero) cells.

Having specified the zeros and ones on the board, and the value of leap (non negative and not bigger than the board size), can we say if the game could be won?

I decided to use the Dynamic Programming approach, since the problem splits naturally in a series of simple steps, each of them contributing to the solution. There is one issue that muddies the water, the backward move. The rest of the algorithm is pretty straightforward.

• Start from the last cell in the board.
• Determine if a pawn could be placed there and if this would lead to a win.
• Move to the next one of its left, up to the leftmost one.
• Then return the win condition for the first cell.

Firstly, I create a cache to store all the intermediate values:

boolean[] memo = new boolean[game.length];
if (game[game.length - 1] == 0)
    memo[memo.length - 1] = true;

They are all initialized to false, but the last one, and only if a pawn could go there.

Having set this initial condition, I could loop on all the other elements, in inverse order

for (int i = memo.length - 2; i >= 0; i--) {
    // ... see below
}

return memo[0];

In the end, the first cell of my cache would contain the solution.

Hold on while reading the following "if", explanation follows.

if (game[i] == 0 && (i + leap >= game.length || memo[i + 1] || memo[i + leap])) {
    memo[i] = true;
    // ... see below
}

First thing, check the current value in the board. If it is not zero, I can't put the pawn there, the cache value stays set to false.

Otherwise, any of the following three conditions lead to true in cache:

• adding the current position to the leap value pushes the pawn out of the board
• the next cell in the board is a good one
• the next leap cell is a good one

Now the funny part. When I set to true a cell, I should ensure that a few cells to the right are marked as good, too. This is due to the backward move. It is a sort of domino effect, that should stop when we find a cell where our pawn can't go.

for (int j = i + 1; j < memo.length && game[j] == 0; j++)
    memo[j] = true;

Full Java code and test case pushed on GitHub.