403. Frog Jump

LeetCode 403. Frog Jump

Description

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.

Example 1:

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:

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.

Constraints:

• 2 <= stones.length <= 2000

• 0 <= stones[i] <= 2^31 - 1

• stones[0] == 0

Tags

Dynamic Programming, Backtracking

Solution

See Reference for Dynamic Programming solutions.

Here we use the DFS strategy and use a stack to store each state rather than recursion. We define the pair{unit, k} to describe the state, and initialize the states stack with []pair{{3, 2}, {2, 1}, {1, 0}} since the problem requires the first jump must be 1 unit. The goal is return true if we can find a pair whose unit is the last element of the input array. When traverse the stack, we ignore pairs that:

• k of whom is 0;

• unit of whom does not exist in the array;

• have been visited (use a set to record).

The remain states pair{pos.unit + pos.k + i, pos.k + i} (-1 ≤ i ≤ 1) would be pushed into the stack. If the goal cannot be reached before the stack becomes empty, we return false.

Complexity

• Time complexity: $O(n^2)$

• Space complexity: $O(n^2)$

Code

func canCross(stones []int) bool {
	if len(stones) < 2 || stones[1] != 1 {
		return false
	}
	// optimization: the frog cannot reach the goal if there exists i that stones[i]-stones[i-1] > i
	for i := 1; i < len(stones); i++ {
		if stones[i]-stones[i-1] > i {
			return false
		}
	}
	unit2idx := map[int]int{}
	for i, u := range stones {
		unit2idx[u] = i
	}
	visited := map[pair]bool{} // remove duplicates
	stack := []pair{{3, 2}, {2, 1}, {1, 0}}
	for len(stack) > 0 {
		pos := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if unit2idx[pos.unit] == len(stones)-1 {
			return true
		}
		if pos.k == 0 || unit2idx[pos.unit] == 0 {
			continue
		}
		for i := -1; i <= 1; i++ {
			p := pair{pos.unit + pos.k + i, pos.k + i}
			if !visited[p] {
				visited[p] = true
				stack = append(stack, p)
			}
		}
	}
	return false
}

Reference

1. 【宫水三叶】一题四解 : 降低确定「记忆化容器大小」的思维难度 & 利用「对偶性质」构造有效状态值

2. 青蛙过河