Hackerrank: Java 1D Array (Part 2)

Java 1D Array (Part 2) is one of the data structure questions in the Java problem set. It is a medium-level question but it is quite challenging because its solution may require you to use a depth-first search (DFS) algorithm. There are various ways to solve this problem, but my solution was to use the recursive DFS algorithm. Here we go.

Here is the link to the problem:

https://www.hackerrank.com/challenges/java-1d-array/problem

The problem is about playing game on a set of arrays that consist of 0's and 1's only. You are standing at index 0 of an n-element array named game.

From some index i, you can perform one of the following moves

• Move Backward: If cell i-1 exists and contains a 0, you can make a move back to the cell.
• Move Forward: 

- If cell i+1 exists and contains a 0, you can make a move forward to the cell.

- If cell i+leap exists and contains a 0, you can jump to the cell i+leap.

- If you are standing in cell n-1, which is the last cell, or your value of i+leap >= n, you can jump off to the end of the array and win the game.

Now, we have the rules.

In other words, you can move from index i to index i-1, i+1 or i+leap  as long as the destination index is a cell containing a "0". If the destination index is greater than n-1, you win the game.

Given  leap and an array game, complete the function in the editor so that it returns true if you can win the game (or false if you cannot).

Input Format

The first line contains an integer, q, denoting the number of queries (i.e., function calls).
The 2*q subsequent lines describe each query over two lines:

1. The first line contains two space-separated integers: n and leap (n:length of game array)
2. The second line contains space-separated binary integers (0 and 1) as the elements of the game array.