1345. Jump Game IV
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]
andi != 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:
1  Input: arr = [100,23,23,404,100,23,23,23,3,404] 
Example 2:
1  Input: arr = [7] 
Example 3:
1  Input: arr = [7,6,9,6,9,6,9,7] 
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)
 When reaching the end, update the
 Each time, try out 3 possibilities,
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 Graphlike 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.
1  while (!q.empty()) 
Code:
1 
