# 1345. Jump Game IV

January 15, 2022

### Description:

Given an array of integers arr, you are initially positioned at the first index of the array.

In one step you can jump from index i to index:

• i + 1 where: i + 1 < arr.length.
• i - 1 where: i - 1 >= 0.
• j where: arr[i] == arr[j] and i != j.

Return the minimum number of steps to reach the last index of the array.

Notice that you can not jump outside of the array at any time.

Example 1:

Example 2:

Example 3:

Constraints:

• 1 <= arr.length <= 5 * 10^4
• -10^8 <= arr[i] <= 10^8

The length of the array is up to 10^4, the algorithm is expected to be bounded by ==O(nlogn)==

### Brute Force:

Each round, you can jump front or back one step, or jump to the place with the same value.

• Traverse all possibilities that start from index 0, with #step = 0, minStep = INT_MAX
• Each time, try out 3 possibilities, #step++
• When reaching the end, update the minStep = min(minStep,#step)

It’s obvious that this method has a factorial time complexity. We can make a little modification, that is, each place can only be visited at most once, or it can’t be the minimum number of steps.

### An Graph-like Intuition:

• Each place is a node on the graph, nodes are sequentially linked according to their order in the array.

• If there are nodes with the same value, link them with an edge.

• Since we can move forward and backward at each place, the graph is a undirected graph.

• Use BFS for solution (Use queue)

In actual implementation, a graph is not necessary, we can just keep. a hash map, where key is the value, value is the position of these values.

### Complexity:

Vertices = N, Edges at max, all nodes have same value, $O(N^2)$, at min, 0.

• Time Complexity: O(V+E)

• Space Complexity: O(V+E) (Use Graph), O(V) (Not using extra graph)

### Problem:

In the implementation, our time complexity depends on the number of edges. In cases of the same value, there could be edges at $O(N^2)$. (All nodes have the same value), which is obviously gonna give us a TLE.

### Solution:

In the BFS Step, after we enqueue nodes with the same value, we can clear the entry in the hash map.