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

• input:
  • array of integers, a
• conditions:
  • 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]
• output:
  • minimum number of steps to reach len(a)-1 from 0
• constraints:
  • 1 <= arr.length <= 5 * 104
  • -108 <= arr[i] <= 108

0.1. Examples

1. Jump Game IV: First Thoughts

1.0. Neighbors

The first thing I noticed was that we can move from i to i-1, 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)

1.1. DP?

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.

1.2. DFS

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 seen or a visited array – 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

2.0. Intuitions

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.

2.1. Logic

• start exploring from node 0
• keep a track of the current list of nodes, from where we would continue exploring: curr = [0]
• 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 i and 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

3.0. Code

class Solution:
    def minJumps(self, a: List[int]) -> int:
        n = len(a)
        if n <= 1: return 0
        
        time = 0
        curr = [0]
        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

• Time: O(N), to explore all N nodes in the worst case.
• Space: O(N), to store the seen set.

Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.