Jump Game IV | LeetCode | Solution Explained
LeetCode 1345. Jump Game IV is a hard one, but after you read this solution, it’ll feel easy and intuitive. I explain the BFS solution using visuals, in detail. Problem Link.
0. Jump Game IV: Problem Discussion
0.0. IO Format
- array of integers, a
- start from 0
- end at len(a) – 1
- from i, you can jump to either i-1 or i+1 or to any of the elements in a which are = a[i]
- minimum number of steps to reach len(a)-1 from 0
1 <= arr.length <= 5 * 104
-108 <= arr[i] <= 108
1. Jump Game IV: First Thoughts
The first thing I noticed was that we can move from
i+1 as well as all of the indices j, such that
a[j] = a[i], mathematically. The code would be super simple and will play as a building block for the solutions later on.
d = defaultdict(list) for i, x in enumerate(a): d[x].append(i)
Since we want to minimize the number of steps taken to reach the end of the array, my initial instinct was to think in terms of dynamic programming.
- dp[i] is the minimum number of steps required to reach the ith point
- d[a[i]] has all the indices, j, where a[j] = a[i]
1.1. Issue with DP
DP at its heart assumes that we are basing our knowledge on previously seen information. However, if you observe carefully, all the indices after i, i+1 and maybe even some in d[a[i]] are invalid.
We haven’t really computed the information from i+1 and beyond and so computing dp[i] that way is incomplete … and also wrong XD.
Logically, if we had the answers for >= i+1 indices in the dp, we would have the answer for dp[n-1] already computed too – which we don’t have.
As I sat in disappointment, I suddenly noticed something – the edges/arrows do look quite a bit like edges. So what if we treated each number as a node?
Then, the “neighbors” term would actually make sense (read the 1.0. section again :P).
- So each number in the array is a node.
- Each node is connected to its adjacent nodes (as in the array)
- And each node is also connected to its neighbors as defined in
d, using d[a[i]]
1.3. Issues with DFS
This was a lot harder to figure out – I even coded it up with WA, MLE and TLEs 🙁
So what’s wrong?
- A classic mistake is to get stuck in an eternal loop – from i, you can go to i+1 and from i+1 in the next iteration, you may end up at i. This can go on forever.
- Fixing the issue above is simple: create a
visitedarray – and as soon as we see an element previously seen, we can return +inf as the cost – we have already seen it, so why see it again?
- However, fixing the issue creates another (classic computer science eh) – if we have explored one path through a particular node, we can’t go through the node again – since it has been marked visited. However, there may be a shorter path through this node.
- Then, could we use backtracking? Well that has its own issues – think why!
In any case, thinking about the problem in terms of a graph was a good idea, and traversing the nodes could get us the answer. Then, how about we try out BFS?
2. Jump Game IV: BFS Logic
We already saw the intuitions for thinking about BFS and why DP and DFS won’t work. Before we start coding, let’s go over a few logical necessities.
- start exploring from node 0
- keep a track of the current list of nodes, from where we would continue exploring:
curr = 
- keep a track of which time-step we are in, which is the number of moves taken to reach to a point:
time = 0
- keep a track of which all nodes we have seen – so as to not go over the nodes already seen:
seen = set()
- once explored an index
iand put all the
js in the next curr, reset the d[a[i]].
Without the last point, we would fail in a case like
[7,7,7,...,7,1], where in the first iteration, we would have seen all the 7s, and added them to the seen set.
But in the second iteration, we would end up going in the for loop again, iterating over all the other 7s – only to be
continued in the if condition. Sounds wasteful, yea? So just do:
d[a[i]] = .
3. Jump Game IV: Optimized Implementation
class Solution: def minJumps(self, a: List[int]) -> int: n = len(a) if n <= 1: return 0 time = 0 curr =  seen = set() d = defaultdict(list) for i, x in enumerate(a): d[x].append(i) while curr: time += 1 temp =  for i in curr: for j in d[a[i]] + [i-1, i+1]: if j in seen: continue else: seen.add(j) if j == n - 1: return time elif 0 <= j < n: temp.append(j) d[a[i]] =  curr = temp return time
3.1. Complexity Analysis
O(N), to explore all N nodes in the worst case.
O(N), to store the seen set.
June 13, 2022