Java 1D Array (Part 2)

  • + 38 comments

    Java solution - passes 100% of test cases

    Solution is basically to do a depth-first search (DFS). Instead of creating a "visited" array, we can mark each array value as 1 when visiting it.

    Full code available at my HackerRank solutions. Here is the main snippet:

    public static boolean canWin(int leap, int[] game) {
        return isSolvable(leap, game, 0);
    }
    
    private static boolean isSolvable(int leap, int[] game, int i) {
        // Base Cases
        if (i >= game.length) {
            return true;
        } else if (i < 0 || game[i] == 1) {
            return false;
        }
                
        game[i] = 1; // marks as visited
    
        // Recursive Cases
        return isSolvable(leap, game, i + leap) || 
               isSolvable(leap, game, i + 1) || 
               isSolvable(leap, game, i - 1);
    }
    

    Let me know if you have any questions.