Frog Jump

hard array dp

Problem

A frog starts at stone 0 with first jump length 1. From any stone after a jump of length k it can next jump k−1, k, or k+1 (jump must be positive). Given the sorted positions of all stones, decide whether the frog can reach the last stone.

Inputstones = [0,1,3,5,6,8,12,17]

Outputtrue

1 → 3 (jump 2), 3 → 5 (2), 5 → 8 (3), 8 → 12 (4), 12 → 17 (5).

stones (sorted, comma-separated)

def can_cross(stones):
    pos = {s: set() for s in stones}
    pos[0].add(0)
    for s in stones:
        for k in pos[s]:
            for jump in (k - 1, k, k + 1):
                if jump > 0 and (s + jump) in pos:
                    pos[s + jump].add(jump)
    return len(pos[stones[-1]]) > 0

function canCross(stones) {
  const pos = new Map();
  for (const s of stones) pos.set(s, new Set());
  pos.get(0).add(0);
  for (const s of stones) {
    for (const k of pos.get(s)) {
      for (const jump of [k - 1, k, k + 1]) {
        if (jump > 0 && pos.has(s + jump)) pos.get(s + jump).add(jump);
      }
    }
  }
  return pos.get(stones[stones.length - 1]).size > 0;
}

class Solution {
    public boolean canCross(int[] stones) {
        Map<Integer, Set<Integer>> pos = new HashMap<>();
        for (int s : stones) pos.put(s, new HashSet<>());
        pos.get(0).add(0);
        for (int s : stones) {
            for (int k : pos.get(s)) {
                for (int j = k - 1; j <= k + 1; j++) {
                    if (j > 0 && pos.containsKey(s + j)) pos.get(s + j).add(j);
                }
            }
        }
        return !pos.get(stones[stones.length - 1]).isEmpty();
    }
}

bool canCross(vector<int>& stones) {
    unordered_map<int, unordered_set<int>> pos;
    for (int s : stones) pos[s] = {};
    pos[0].insert(0);
    for (int s : stones) {
        for (int k : pos[s]) {
            for (int j = k - 1; j <= k + 1; j++) {
                if (j > 0 && pos.count(s + j)) pos[s + j].insert(j);
            }
        }
    }
    return !pos[stones.back()].empty();
}

Explanation

The frog's next move depends on how it arrived: after a jump of length k it can next jump k-1, k, or k+1. So just knowing which stone we're on isn't enough — we also need the jump lengths that could have landed us there.

We build a map pos where pos[s] is the set of jump lengths that can reach stone s. The frog starts at stone 0 having "arrived" with jump 0, so we seed pos[0] = {0}.

We then sweep the stones left to right. For each stone s and each arrival jump k recorded there, we try the three next jumps k-1, k, k+1. If a jump is positive and lands on a real stone, we add that jump length to that stone's set.

At the end, the frog can finish exactly when the last stone has any recorded jump, i.e. pos[last] is non-empty.

Example: stones = [0,1,3,5,6,8,12,17]. The path 1 → 3 (jump 2) → 5 (2) → 8 (3) → 12 (4) → 17 (5) fills in jump sets all the way to 17, so the answer is true.

Time: O(n²) Space: O(n²)