Photo by Mika Baumeister on Unsplash

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: 3
Explanation: 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 = [7]
Output: 0
Explanation: 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: 1
Explanation: 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.

If you like the content please follow me here @medium and at LinkedIn

https://www.linkedin.com/in/jaydeep-shil-75a90847

Full Stack Programmer, love to solve problem’s during free time.