Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Frog Jump

HARDProblemSolveExternal Links

Description

A frog is trying to cross a river. The river is divided into units, and at certain positions along the river there are stones. The frog can only land on stones — it cannot land in the water.

The frog starts on the first stone (position 0) and wants to reach the last stone. However, the frog's jumping ability follows a strict rule:

  • The first jump must be exactly 1 unit
  • If the frog's previous jump was k units, then its next jump must be either k-1, k, or k+1 units
  • The frog can only jump forward (to a higher position)
  • The frog must land on a stone — it cannot jump into water

Given a list of stone positions sorted in ascending order, determine if the frog can successfully reach the last stone.

Return true if the frog can cross, false otherwise.

Examples

Example 1

Input: stones = [0, 1, 3, 5, 6, 8, 12, 17]

Output: true

Explanation: The frog can cross by taking these jumps:

  • Jump 1 unit: position 0 → position 1
  • Jump 2 units: position 1 → position 3
  • Jump 2 units: position 3 → position 5
  • Jump 3 units: position 5 → position 8
  • Jump 4 units: position 8 → position 12
  • Jump 5 units: position 12 → position 17

Each jump size is within k±1 of the previous jump (1→2→2→3→4→5). The frog builds momentum gradually, never violating the jump rule.

Example 2

Input: stones = [0, 1, 2, 3, 4, 8, 9, 11]

Output: false

Explanation: There is no way for the frog to jump from position 4 to position 8. The gap is 4 units, but the frog can only reach position 4 with a small jump size (at most k=2 from position 2 or k=1 from position 3). With k=2, the max next jump is k+1=3, reaching at most position 7. With k=1, the max next jump is 2, reaching at most position 6. Neither bridges the gap to position 8.

Constraints

  • 2 ≤ stones.length ≤ 2000
  • 0 ≤ stones[i] ≤ 2^31 - 1
  • stones[0] == 0
  • stones is sorted in strictly increasing order

Editorial

Brute Force

Intuition

The most straightforward approach is to try every possible path the frog could take and see if any of them lead to the last stone.

At each stone, the frog has a choice: if its last jump was k units, it can try jumping k-1, k, or k+1 units forward. If any of those landing positions has a stone, we recursively explore from that new position. If we ever reach the last stone, we return true. If all paths from a stone are dead ends, we backtrack and try a different route.

Think of it like navigating a maze. At every intersection (stone), you have up to three corridors (jump sizes) to choose from. You pick one, walk down it, and if it leads to a wall (water or no stone), you come back and try another corridor. This exhaustive exploration guarantees finding a solution if one exists — but it may explore an enormous number of paths before concluding.

Step-by-Step Explanation

Let's trace the DFS on stones = [0, 1, 2, 3, 4, 8, 9, 11]:

Step 1: Start at stone 0 (position 0) with last jump k=0. The only valid next jump is k+1=1 (since k-1=-1 and k=0 are invalid).

Step 2: Jump 1 unit to position 1 — stone exists! Now at position 1, k=1. Can try jumps of size 1 or 2 (k-1=0 is invalid).

Step 3: Try jump=1 → position 2 — stone exists. Explore DFS(pos=2, k=1).

Step 4: At position 2, k=1. Try jump=1 → position 3 — stone exists. Explore DFS(pos=3, k=1).

Step 5: At position 3, k=1. Try jump=1 → position 4 — stone exists. Explore DFS(pos=4, k=1).

Step 6: At position 4, k=1. Try jump=1 → position 5 — NO stone! Try jump=2 → position 6 — NO stone! Dead end. The gap from position 4 to the next stone at 8 is too large.

Step 7: Backtrack to position 3. Try jump=2 → position 5 — NO stone. All options from (pos=3, k=1) exhausted. Dead end.

Step 8: Backtrack to position 2. Try jump=2 → position 4 — stone exists. Explore DFS(pos=4, k=2).

Step 9: At position 4, k=2. Try jump=1 → pos 5 (no), jump=2 → pos 6 (no), jump=3 → pos 7 (no). Dead end! Even with k=2, the max jump k+1=3 only reaches position 7, but the next stone is at position 8.

Step 10: Backtrack to position 1. Try jump=2 → position 3 — stone exists. Explore DFS(pos=3, k=2).

Step 11: At position 3, k=2. Try jump=1 → pos 4 (leads to dead ends as seen before), jump=2 → pos 5 (no), jump=3 → pos 6 (no). Dead end.

Step 12: All branches exhausted. Return false — the frog cannot cross. The critical bottleneck is the gap between positions 4 and 8.

Brute Force DFS — Exploring All Paths on [0,1,2,3,4,8,9,11] — Watch the recursive DFS explore branches one by one, hitting dead ends at the gap between positions 4 and 8, and backtracking to try alternative paths.

Algorithm

  1. Store all stone positions in a set for O(1) lookup
  2. Define DFS(pos, k) — returns true if the frog can reach the last stone from position pos with last jump k
  3. Base case: if pos == last_stone, return true
  4. For each possible jump size j in {k-1, k, k+1}:
    • If j > 0 (must move forward) and pos + j is a stone position:
      • Recursively call DFS(pos + j, j)
      • If it returns true, return true
  5. If no jump leads to success, return false
  6. Start with DFS(0, 0)

Code

#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
public:
    bool canCross(vector<int>& stones) {
        unordered_set<int> stoneSet(stones.begin(), stones.end());
        int target = stones.back();
        return dfs(stoneSet, 0, 0, target);
    }

private:
    bool dfs(unordered_set<int>& stoneSet, int pos, int k, int target) {
        if (pos == target) return true;
        
        for (int jump = k - 1; jump <= k + 1; jump++) {
            if (jump > 0 && stoneSet.count(pos + jump)) {
                if (dfs(stoneSet, pos + jump, jump, target))
                    return true;
            }
        }
        return false;
    }
};
class Solution:
    def canCross(self, stones):
        stone_set = set(stones)
        target = stones[-1]
        
        def dfs(pos, k):
            if pos == target:
                return True
            
            for jump in range(k - 1, k + 2):
                if jump > 0 and (pos + jump) in stone_set:
                    if dfs(pos + jump, jump):
                        return True
            return False
        
        return dfs(0, 0)
import java.util.*;

class Solution {
    public boolean canCross(int[] stones) {
        Set<Integer> stoneSet = new HashSet<>();
        for (int s : stones) stoneSet.add(s);
        int target = stones[stones.length - 1];
        return dfs(stoneSet, 0, 0, target);
    }
    
    private boolean dfs(Set<Integer> stoneSet, int pos, int k, int target) {
        if (pos == target) return true;
        
        for (int jump = k - 1; jump <= k + 1; jump++) {
            if (jump > 0 && stoneSet.contains(pos + jump)) {
                if (dfs(stoneSet, pos + jump, jump, target))
                    return true;
            }
        }
        return false;
    }
}

Complexity Analysis

Time Complexity: O(3^n)

At each stone, the frog can branch into up to 3 paths (jump k-1, k, or k+1). In the worst case, the recursion tree has depth n (number of stones), and each level branches 3 ways. This gives 3^n total states to explore.

In practice, many branches terminate early when positions have no stones, but the worst case remains exponential. For n = 2000, 3^2000 is astronomically large — the algorithm would never finish.

Space Complexity: O(n)

The recursion stack can go at most n levels deep (one stone per level in the longest branch). The hash set of stone positions uses O(n) space.

Why This Approach Is Not Efficient

The brute force DFS explores an exponential number of paths because it recomputes the same states repeatedly. The state of the algorithm is defined by two values: the current position and the last jump size. The same (position, jump) pair can be reached via many different paths, and each time we encounter it, we re-explore all subsequent branches from scratch.

For example, DFS(4, k=1) might be called from DFS(3, k=1) along one path, and from DFS(3, k=2) along another. Without memoization, both calls independently explore the full subtree below DFS(4, 1).

With n up to 2000 stones, the exponential 3^n blowup makes this approach completely impractical. We need to remember the results of subproblems so we never solve the same (position, jump) pair twice.

Key insight: There are at most n possible positions and at most O(n) possible jump sizes at each position. This means the total number of unique (position, jump) states is at most O(n²). If we store results for each state the first time we compute it, we reduce the total work from exponential to polynomial.

Optimal Approach - Dynamic Programming with Hash Map

Intuition

Instead of exploring paths top-down with recursion, we can work bottom-up iteratively. For each stone, we maintain a set of jump sizes that can reach that stone. Then, for each jump size in the set, we try the three possible next jumps (k-1, k, k+1) and propagate them to future stones.

The algorithm works like a wave spreading forward:

  1. Start: the frog is at stone 0 with a "jump of 0"
  2. For each stone in left-to-right order, look at all the jump sizes that brought the frog here
  3. For each such jump size k, try jumping k-1, k, or k+1 units forward
  4. If the landing position has a stone, record this new jump size in that stone's set
  5. At the end, if the last stone's set is non-empty, the frog can reach it

Think of it like spreading rumours through a network. Each stone tells the next reachable stones: "the frog can arrive here with jump sizes of 2 and 3." Those stones then propagate further. If the rumour reaches the last stone, the frog can cross.

The critical optimization is using a hash map to store the sets: we map each stone position to its set of possible arriving jump sizes. This gives O(1) position lookups and avoids recomputation.

Step-by-Step Explanation

Let's trace with stones = [0, 1, 3, 5, 6, 8, 12, 17]:

Step 1: Initialize: each stone maps to an empty set of jump sizes. Set dp[0] = {0} (frog starts here with "jump 0").

Step 2: Process stone 0: k=0. Only valid jump: k+1=1 → target = 0+1 = 1. Stone exists! dp[1] = {1}.

Step 3: Process stone 1: k=1. Try k=1 → pos 2 (no stone, miss). Try k+1=2 → pos 3. Stone exists! dp[3] = {2}.

Step 4: Process stone 3: k=2. Try k=2 → pos 5. Stone! dp[5] = {2}. Try k+1=3 → pos 6. Stone! dp[6] = {3}.

Step 5: Process stone 5: k=2. Try k-1=1 → pos 6. Stone! dp[6] = {3, 1}. Try k+1=3 → pos 8. Stone! dp[8] = {3}.

Step 6: Process stone 6: k=3, try k-1=2 → pos 8. Stone! dp[8] = {3, 2}. k=1, try k+1=2 → pos 8 (already has 2). Other jumps miss.

Step 7: Process stone 8: k=3, try k+1=4 → pos 12. Stone! dp[12] = {4}. k=2, try k-1=1 → 9 (no), k=2 → 10 (no), k+1=3 → 11 (no). All miss.

Step 8: Process stone 12: k=4, try k+1=5 → pos 17. Stone! dp[17] = {5}.

Step 9: Check last stone (position 17): dp[17] = {5} is non-empty → the frog can cross!

Step 10: One valid path: 0→1 (jump 1) → 3 (jump 2) → 5 (jump 2) → 8 (jump 3) → 12 (jump 4) → 17 (jump 5). Each jump size is within k±1 of the previous.

Bottom-Up DP — Propagating Reachable Jumps Across Stones — Watch as each stone propagates possible jump sizes to future stones. Labels below each stone show the set of jump sizes that can reach it.

Algorithm

  1. Early exit: if the second stone is not at position 1, return false (first jump must be 1)
  2. Create a hash map dp mapping each stone position to an empty set of jump sizes
  3. Initialize dp[0] = {0} (frog starts at position 0 with "jump 0")
  4. For each stone position in left-to-right order:
    • For each jump size k in dp[stone]:
      • For each candidate jump j in {k-1, k, k+1}:
        • If j > 0 and stone + j is a stone position:
          • Add j to dp[stone + j]
  5. Return true if dp[last_stone] is non-empty, false otherwise

Code

#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;

class Solution {
public:
    bool canCross(vector<int>& stones) {
        int n = stones.size();
        if (stones[1] != 1) return false;
        
        // Map each stone position to the set of jump sizes that can reach it
        unordered_map<int, unordered_set<int>> dp;
        for (int s : stones) dp[s] = {};
        dp[0].insert(0);
        
        for (int stone : stones) {
            for (int k : dp[stone]) {
                for (int jump = k - 1; jump <= k + 1; jump++) {
                    if (jump > 0 && dp.count(stone + jump)) {
                        dp[stone + jump].insert(jump);
                    }
                }
            }
        }
        
        return !dp[stones.back()].empty();
    }
};
class Solution:
    def canCross(self, stones):
        if stones[1] != 1:
            return False
        
        # Map each stone position to a set of jump sizes that can reach it
        dp = {s: set() for s in stones}
        dp[0].add(0)
        
        for stone in stones:
            for k in dp[stone]:
                for jump in [k - 1, k, k + 1]:
                    if jump > 0 and (stone + jump) in dp:
                        dp[stone + jump].add(jump)
        
        return len(dp[stones[-1]]) > 0
import java.util.*;

class Solution {
    public boolean canCross(int[] stones) {
        int n = stones.length;
        if (stones[1] != 1) return false;
        
        // Map each stone position to the set of jump sizes that can reach it
        Map<Integer, Set<Integer>> dp = new HashMap<>();
        for (int s : stones) dp.put(s, new HashSet<>());
        dp.get(0).add(0);
        
        for (int stone : stones) {
            for (int k : dp.get(stone)) {
                for (int jump = k - 1; jump <= k + 1; jump++) {
                    if (jump > 0 && dp.containsKey(stone + jump)) {
                        dp.get(stone + jump).add(jump);
                    }
                }
            }
        }
        
        return !dp.get(stones[stones.length - 1]).isEmpty();
    }
}

Complexity Analysis

Time Complexity: O(n²)

There are n stones. For each stone, the number of possible jump sizes in its set is bounded by O(n) — because the maximum jump size to reach any stone is at most n (the frog starts with jump 1 and can increase by at most 1 per stone, so after visiting n stones the max jump is roughly n). Therefore, the total number of (stone, jump_size) pairs across all stones is at most O(n²). For each pair, we do O(1) work (checking 3 candidate jumps and hash map lookups). Total: O(n²).

For n = 2000, this means about 4 million operations — completing in milliseconds.

Space Complexity: O(n²)

The hash map stores up to O(n²) entries across all stones (n stones × up to O(n) jump sizes per stone). The hash set of stone positions uses O(n) additional space. Dominant term: O(n²).

This is a massive improvement over the brute force O(3^n) approach. The key is that we process each unique (stone, jump_size) state exactly once, avoiding all the redundant exploration that plagues the recursive approach.