Frog Jump

Problem

A frog is crossing a river. The river is divided into some number of units, and at each unit, there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.

Given a list of stones’ positions (in units) in sorted ascending order, determine if the frog can cross the river by landing on the last stone. Initially, the frog is on the first stone and assumes the first jump must be 1 unit.

If the frog’s last jump was k units, its next jump must be either k - 1, k, or k + 1 units. The frog can only jump in the forward direction.

Part 2 - Frog Jump II

Examples

Example 1:

1
2
3


Input: stones = [0,1,3,5,6,8,12,17]
Output: true
Explanation: The frog can jump to the last stone by jumping 1 unit to the 2nd stone, then 2 units to the 3rd stone, then 2 units to the 4th stone, then 3 units to the 6th stone, 4 units to the 7th stone, and 5 units to the 8th stone.

Example 2:

1
2
3


Input: stones = [0,1,2,3,4,8,9,11]
Output: false
Explanation: There is no way to jump to the last stone as the gap between the 5th and 6th stone is too large.

Solution

Method 1 – Naive DFS

Intuition

The key idea is to try every possible jump the frog can make at each stone, recursively exploring all valid paths. If any path leads to the last stone, return true. This brute-force approach checks all combinations, which is inefficient but simple to implement.

Approach

Use a recursive DFS function that tracks the current stone index and the last jump distance.
At each step, try jumps of k-1, k, and k+1 units (where k is the last jump), skipping non-positive jumps.
For each possible jump, check if the resulting position is a stone (using a set for O(1) lookup).
If the frog reaches the last stone, return true.
If all paths are exhausted without reaching the last stone, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution {
public:
	bool canCross(vector<int>& stones) {
		unordered_set<int> stoneSet(stones.begin(), stones.end());
		int last = stones.back();
		function<bool(int, int)> dfs = [&](int pos, int k) {
			if (pos == last) return true;
			for (int jump = k - 1; jump <= k + 1; ++jump) {
				if (jump > 0 && stoneSet.count(pos + jump)) {
					if (dfs(pos + jump, jump)) return true;
				}
			}
			return false;
		};
		return dfs(0, 0);
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


type Solution struct{}

func (Solution) CanCross(stones []int) bool {
	stoneSet := make(map[int]struct{})
	for _, s := range stones {
		stoneSet[s] = struct{}{}
	}
	last := stones[len(stones)-1]
	var dfs func(pos, k int) bool
	dfs = func(pos, k int) bool {
		if pos == last {
			return true
		}
		for jump := k - 1; jump <= k+1; jump++ {
			if jump > 0 {
				if _, ok := stoneSet[pos+jump]; ok {
					if dfs(pos+jump, jump) {
						return true
					}
				}
			}
		}
		return false
	}
	return dfs(0, 0)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
	fun canCross(stones: IntArray): Boolean {
		val stoneSet = stones.toSet()
		val last = stones.last()
		fun dfs(pos: Int, k: Int): Boolean {
			if (pos == last) return true
			for (jump in k - 1..k + 1) {
				if (jump > 0 && (pos + jump) in stoneSet) {
					if (dfs(pos + jump, jump)) return true
				}
			}
			return false
		}
		return dfs(0, 0)
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution:
	def canCross(self, stones: list[int]) -> bool:
		stone_set: set[int] = set(stones)
		last: int = stones[-1]
		def dfs(pos: int, k: int) -> bool:
			if pos == last:
				return True
			for jump in (k - 1, k, k + 1):
				if jump > 0 and (pos + jump) in stone_set:
					if dfs(pos + jump, jump):
						return True
			return False
		return dfs(0, 0)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


struct Solution;

impl Solution {
	pub fn can_cross(stones: Vec<i32>) -> bool {
		use std::collections::HashSet;
		let stone_set: HashSet<i32> = stones.iter().cloned().collect();
		let last = *stones.last().unwrap();
		fn dfs(pos: i32, k: i32, stone_set: &HashSet<i32>, last: i32) -> bool {
			if pos == last {
				return true;
			}
			for jump in [k - 1, k, k + 1] {
				if jump > 0 && stone_set.contains(&(pos + jump)) {
					if dfs(pos + jump, jump, stone_set, last) {
						return true;
					}
				}
			}
			false
		}
		dfs(0, 0, &stone_set, last)
	}
}

Complexity

Time: O(3^n) in the worst case, as each stone can branch into up to 3 recursive calls.
Space: O(n) for the recursion stack and stone set.

Method 2 – DFS with Memoization

Intuition

The naive DFS approach recalculates the same subproblems multiple times, leading to exponential time. By storing the results of subproblems (i.e., the answer for a given stone and last jump), we avoid redundant work. This optimization, called memoization, drastically reduces the number of recursive calls.

Approach

Use a recursive DFS function that takes the current position and last jump as parameters.
Store results of subproblems in a memoization table (e.g., a map or dictionary) keyed by (position, last_jump).
At each step, try jumps of k-1, k, and k+1 units, skipping non-positive jumps.
For each valid jump, check if the resulting position is a stone.
If the frog reaches the last stone, return true.
If all paths from the current state fail, store and return false.
Start DFS from the first stone with a jump of 0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
public:
	bool canCross(vector<int>& stones) {
		unordered_set<int> stoneSet(stones.begin(), stones.end());
		int last = stones.back();
		unordered_map<long long, bool> memo;
		function<bool(int, int)> dfs = [&](int pos, int k) {
			long long key = ((long long)pos << 32) | k;
			if (memo.count(key)) return memo[key];
			if (pos == last) return true;
			for (int jump = k - 1; jump <= k + 1; ++jump) {
				if (jump > 0 && stoneSet.count(pos + jump)) {
					if (dfs(pos + jump, jump)) return memo[key] = true;
				}
			}
			return memo[key] = false;
		};
		return dfs(0, 0);
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


type Solution struct{}

func (Solution) CanCross(stones []int) bool {
	stoneSet := make(map[int]struct{})
	for _, s := range stones {
		stoneSet[s] = struct{}{}
	}
	last := stones[len(stones)-1]
	memo := make(map[[2]int]bool)
	var dfs func(pos, k int) bool
	dfs = func(pos, k int) bool {
		key := [2]int{pos, k}
		if v, ok := memo[key]; ok {
			return v
		}
		if pos == last {
			return true
		}
		for jump := k - 1; jump <= k+1; jump++ {
			if jump > 0 {
				if _, ok := stoneSet[pos+jump]; ok {
					if dfs(pos+jump, jump) {
						memo[key] = true
						return true
					}
				}
			}
		}
		memo[key] = false
		return false
	}
	return dfs(0, 0)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution {
	public boolean canCross(int[] stones) {
		Set<Integer> stoneSet = new HashSet<>();
		for (int s : stones) stoneSet.add(s);
		int last = stones[stones.length - 1];
		Map<String, Boolean> memo = new HashMap<>();
		return dfs(0, 0, stoneSet, last, memo);
	}
	private boolean dfs(int pos, int k, Set<Integer> stoneSet, int last, Map<String, Boolean> memo) {
		String key = pos + "," + k;
		if (memo.containsKey(key)) return memo.get(key);
		if (pos == last) return true;
		for (int jump = k - 1; jump <= k + 1; jump++) {
			if (jump > 0 && stoneSet.contains(pos + jump)) {
				if (dfs(pos + jump, jump, stoneSet, last, memo)) {
					memo.put(key, true);
					return true;
				}
			}
		}
		memo.put(key, false);
		return false;
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution {
	fun canCross(stones: IntArray): Boolean {
		val stoneSet = stones.toSet()
		val last = stones.last()
		val memo = mutableMapOf<Pair<Int, Int>, Boolean>()
		fun dfs(pos: Int, k: Int): Boolean {
			val key = pos to k
			memo[key]?.let { return it }
			if (pos == last) return true
			for (jump in k - 1..k + 1) {
				if (jump > 0 && (pos + jump) in stoneSet) {
					if (dfs(pos + jump, jump)) {
						memo[key] = true
						return true
					}
				}
			}
			memo[key] = false
			return false
		}
		return dfs(0, 0)
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution:
	def canCross(self, stones: list[int]) -> bool:
		stone_set: set[int] = set(stones)
		last: int = stones[-1]
		memo: dict[tuple[int, int], bool] = {}
		def dfs(pos: int, k: int) -> bool:
			key = (pos, k)
			if key in memo:
				return memo[key]
			if pos == last:
				return True
			for jump in (k - 1, k, k + 1):
				if jump > 0 and (pos + jump) in stone_set:
					if dfs(pos + jump, jump):
						memo[key] = True
						return True
			memo[key] = False
			return False
		return dfs(0, 0)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


struct Solution;

impl Solution {
	pub fn can_cross(stones: Vec<i32>) -> bool {
		use std::collections::{HashSet, HashMap};
		let stone_set: HashSet<i32> = stones.iter().cloned().collect();
		let last = *stones.last().unwrap();
		fn dfs(pos: i32, k: i32, stone_set: &HashSet<i32>, last: i32, memo: &mut HashMap<(i32, i32), bool>) -> bool {
			let key = (pos, k);
			if let Some(&ans) = memo.get(&key) {
				return ans;
			}
			if pos == last {
				return true;
			}
			for jump in [k - 1, k, k + 1] {
				if jump > 0 && stone_set.contains(&(pos + jump)) {
					if dfs(pos + jump, jump, stone_set, last, memo) {
						memo.insert(key, true);
						return true;
					}
				}
			}
			memo.insert(key, false);
			false
		}
		let mut memo = HashMap::new();
		dfs(0, 0, &stone_set, last, &mut memo)
	}
}

Complexity

Time: O(n^2) where n is the number of stones, since each state (position, last_jump) is computed at most once.
Space: O(n^2) for the memoization table and recursion stack.

Method 3 – Bottom-Up Dynamic Programming

Intuition

Instead of solving the problem recursively and memoizing subproblems, we can build up the solution iteratively. For each stone, we track all possible jump sizes that can reach it. If the last stone is reachable with any jump, the answer is true.

Approach

Create a map from stone positions to a set of possible jump sizes that can reach that stone.
Initialize the first stone (position 0) with a jump size of 0.
For each stone, iterate through all jump sizes that can reach it.
For each jump size k, try jumps of k-1, k, and k+1 (skip non-positive).
If the resulting position is a stone, add the jump size to its set.
After processing, check if the last stone’s set is non-empty.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


type Solution struct{}

func (Solution) CanCross(stones []int) bool {
	dp := make(map[int]map[int]struct{})
	for _, s := range stones {
		dp[s] = make(map[int]struct{})
	}
	dp[0][0] = struct{}{}
	for _, s := range stones {
		for k := range dp[s] {
			for d := k - 1; d <= k+1; d++ {
				if d > 0 {
					if _, ok := dp[s+d]; ok {
						dp[s+d][d] = struct{}{}
					}
				}
			}
		}
	}
	return len(dp[stones[len(stones)-1]]) > 0
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
	fun canCross(stones: IntArray): Boolean {
		val dp = stones.associateWith { mutableSetOf<Int>() }.toMutableMap()
		dp[0]?.add(0)
		for (s in stones) {
			for (k in dp[s]!!) {
				for (d in k - 1..k + 1) {
					if (d > 0 && dp.containsKey(s + d)) {
						dp[s + d]?.add(d)
					}
				}
			}
		}
		return dp[stones.last()]!!.isNotEmpty()
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution:
	def canCross(self, stones: list[int]) -> bool:
		dp: dict[int, set[int]] = {s: set() for s in stones}
		dp[0].add(0)
		for s in stones:
			for k in dp[s]:
				for d in (k - 1, k, k + 1):
					if d > 0 and (s + d) in dp:
						dp[s + d].add(d)
		return bool(dp[stones[-1]])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


struct Solution;

impl Solution {
	pub fn can_cross(stones: Vec<i32>) -> bool {
		use std::collections::{HashMap, HashSet};
		let mut dp: HashMap<i32, HashSet<i32>> = stones.iter().map(|&s| (s, HashSet::new())).collect();
		dp.get_mut(&0).unwrap().insert(0);
		for &s in &stones {
			let jumps: Vec<i32> = dp[&s].iter().cloned().collect();
			for k in jumps {
				for d in [k - 1, k, k + 1] {
					if d > 0 {
						if let Some(set) = dp.get_mut(&(s + d)) {
							set.insert(d);
						}
					}
				}
			}
		}
		!dp[stones.last().unwrap()].is_empty()
	}
}

Complexity

Time: O(n^2) where n is the number of stones, since each stone can have up to n possible jump sizes.
Space: O(n^2) for the map storing jump sizes for each stone.

Problem#

Examples#

Solution#

Method 1 – Naive DFS#

Intuition#

Approach#

Code#

Complexity#

Method 2 – DFS with Memoization#

Intuition#

Approach#

Code#

Complexity#

Method 3 – Bottom-Up Dynamic Programming#

Intuition#

Approach#

Code#

Complexity#

Problem

Examples

Solution

Method 1 – Naive DFS

Intuition

Approach

Code

Complexity

Method 2 – DFS with Memoization

Intuition

Approach

Code

Complexity

Method 3 – Bottom-Up Dynamic Programming

Intuition

Approach

Code

Complexity