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

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

• `i + 1` where: `i + 1 < arr.length`.

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:

`Input: arr = [100,-23,-23,404,100,23,23,23,3,404]Output: 3Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.`

Example 2:

`Input: arr = Output: 0Explanation: Start index is the last index. You don't need to jump.`

Example 3:

`Input: arr = [7,6,9,6,9,6,9,7]Output: 1Explanation: You can jump directly from index 0 to index 7 which is last index of the array.`

Example 4:

`Input: arr = [6,1,9]Output: 2`

Example 5:

`Input: arr = [11,22,7,7,7,7,7,7,7,22,13]Output: 3`

Constraints:

• `1 <= arr.length <= 5 * 104`
• One can jump from step `i` to step `i + 1`, where `i + 1 < n`.

For example, consider the following mini-game and its solution:

In the example given above, four jumps are needed to reach the end. The `k` array for this example will be ,`[2, 5, 7, 5, 3, 4] `and your function should return `4` as output.

# Solution

This problem can be mapped as a graph problem in which we need to find the shortest path between two vertices. So, to solve this problem, we will use a breadth-first search.

• First, we will build a graph. This will be an unweighted, undirected graph, and the indices of `k` will represent nodes.

# Time complexity

The time complexity will be O(n) because we visit every node at most once.

# Space complexity

The space complexity will be O(n) because we store nodes in the hash.