Frog Jump

Question (LC.403)

Given an increasing sequence of stone positions, determine the doability jumping from the first stone to the last one. The first jump is always 1. The next jump can be k-1, k, or k+1.

Clarification

What are the numbers not in the sequence? They are water positions (not jumpable). How large will the stone sequence be? The number of stones is between 2 to 1100. We will at least have the starting stone and the ending stone right? Yes. The first stone is always at pos 0.

Examples

I: [0,1,3,5,6,8,12,17]
O: True

I: [0,1,2,3,4,8,9,11]
O: False (4 and 8 is too large for one jump)

I: [0, INT_MAX]
O: False

Analysis

This is a doability problem ({0,1} guarantees optimal substructure). And subproblems are overlapping (draw out an example). The subproblem needs to be more specific than just the landing position. The jump steps that are required to get there need to be in the state as well.

DP Approach

1. Define State
    F[i][k] = the doability of landing at ith stone with jumping ability k

2. Recursive Calls
    F[n][k] = OR(F[n-k][k-1], F[n-k][k], F[n-k][k+1])

3. Base Case
    F[0][1] = True

4. Topo Order (row by row, stone by stone)
    for i from 1 to stonePos.length - 1
        sPos = stonePos[i]
        for k from 1 to sPos - 1
        F[sPos][k] = OR(F[sPos-k][k-1], F[sPos-k][k], F[sPos-k][k+1])

5. Final Answer (last row)
    for k from 1 to n-1
        if F[n][k]: return true

Code 1.0

public boolean canCross(int[] stonePos) {
    // edge check
    if (stonePos == null || stonePos.length < 2) {
        return true;
    }
    // create memo table
    int endStone = stonePos[stonePos.length-1];
    // +2 because of the 3-way dependency requires one more state (from the right)
    boolean[][] memo = new boolean[endStone + 2][endStone + 2];
    // init base case
    memo[0][1] = true;
    // topo order
    for (int i = 1; i < stonePos.length; i++) {
        int sPos = stonePos[i];
        for (int k = 1; k <= sPos; k++) {
            memo[sPos][k] = memo[sPos-k][k-1] || memo[sPos-k][k] || memo[sPos-k][k+1];
        }
    }
    // final answer
    for (int k = 1; k <= endStone; k++) {
        if (memo[endStone][k]) return true;
    }
    return false;
}

This block of code will get Memory Limit Exceeded. The online judge offers the following hint

Your code cost too much memory than we expected. Check your space complexity. Memory limit exceeded usually caused by you create a 2D-array which is unnecessary.

Reducing Space Complexity

From the state graph, the rows that are water rows can certainly be reduced. We can take advantage of the resizing ability of HashMap to store the stone rows as keys. We can save space from the columns as well. We can use a HashSet to store all the possible jumps to get to that row.

Code 2.0