HackerRank Java 1D Array (Part 2)

Question

I am trying to solve the following question HackerRank Java 1D Array

I have come up with the following backtracking approach.

import java.util.Scanner;

public class Solution {
static int arr[];

public static void main(String[] args) {    
    Scanner sc= new Scanner(System.in);
    int T = sc.nextInt();
    for (int j= 0; j < T; j++) {
        int n = sc.nextInt();
        arr = new int[n];
        int m = sc.nextInt();
        for (int k = 0; k< n; k++) {
            arr[k]= sc.nextInt();
        }
       if(canReach(0,arr.length,m))
           System.out.println("YES");
       else 
          System.out.println("NO");
    }
}
public static boolean canReach(int src,int dest,int m)
{
    if(src>=(dest-1)||(src+m)>=dest)
        return true;
    if(isValidDest(src+1)&&canReach(src+1, dest, m))
        return true;
    if(isValidDest(src-1)&&canReach(src-1, dest, m))
        return true;
    if(isValidDest(src+m)&&canReach(src+m, dest, m))
        return true;
    return false;
}
private static boolean isValidDest(int dest) {
    if(((dest>=0&&dest<arr.length)&&(arr[dest]==0)))
        return true;
    return false;
}

}

But I am getting a stack-overflow error for the following test case 0 0 1 1 1 0.

Could anyone help me out on how to avoid this stack-overflow error, while keeping intact the backtracking approach.

Modified code (solution)

import java.util.Scanner;

public class Solution {
static int arr[];
static boolean isDestVisited[];

public static void main(String[] args) {    
    Scanner sc= new Scanner(System.in);
    int T = sc.nextInt();
    for (int j= 0; j < T; j++) {
        int n = sc.nextInt();
        arr = new int[n];
        isDestVisited = new boolean[n];
        int m = sc.nextInt();
        for (int k = 0; k< n; k++) {
            arr[k]= sc.nextInt();
        }
       if(canReach(0,arr.length,m))
           System.out.println("YES");
       else 
          System.out.println("NO");
    }
}
public static boolean canReach(int src,int dest,int m)
{
    if(src>=(dest-1)||(src+m)>=dest)
        return true;
    if(isDestVisited[src]==true)
        return false;
    isDestVisited[src]=true;
    if(isValidDest(src+1)&&canReach(src+1, dest, m))
        return true;
    if(isValidDest(src-1)&&canReach(src-1, dest, m))
        return true;
    if(isValidDest(src+m)&&canReach(src+m, dest, m))
        return true;
    isDestVisited[src]=false;
    return false;
}
private static boolean isValidDest(int dest) {
    if(((dest>=0&&dest<arr.length)&&(arr[dest]==0)))
        return true;
    return false;
}

}

Answer 1

In recursive algo you must to avoid processing of same state twice

if (src >= dest)
    return true;
if (thisPositionAlreadyTested[src])
  return false;
thisPositionAlreadyTested[src] = true;
if ( ...

or you can reuse arr[] content for same purpose if you can modify it