Simple Java Solution - Recursion + Binary Search with Comments


  • 0
    C

    Start from the beginning. At a stone that we reached with a jump k, try each jump j that is possible (k - 1, k, k + 1). For that jump, calculate the stone p that we would land up. Binary search if that stone exists in the rest of the array (since it is sorted). If so, jump to that stone with our new 'k'. See if we can get to the last stone. Else backtrack.

    public boolean canCross(int[] stones) {
        int k = 0;
        return canReachEnd(stones, 0, k);
    }
    
    private boolean canReachEnd(int[] stones, int i, int k) {
        if (i == stones.length - 1) return true;
        
        for (int j = k - 1; j <= k + 1; j++) {
            int p = stones[i] + j;
            int q = Arrays.binarySearch(stones, i + 1, stones.length, p);
            if (q > 0) {
                if (canReachEnd(stones, q, j)) return true;
            }
        }
        
        return false;
    }
    

    I'm not sure but I think the worst-case time complexity is 3^(stones.length). Can optimize by caching the result for a given i and k.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.