Jump Game II

Photo by Nicolas Picard on Unsplash

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [2,3,0,1,4]
Output: 2

Constraints:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 1000

Solution

  1. Initialize the maximum position that one could reach and the maximum position reachable during the first hop as maxIndexReach = nums[0] and currentIndexReach = nums[0] respectively.
  2. If the size of our array is greater than 1, then initialize the maxJumps variable to 1.
  3. Start iterating over the array.
  4. In each iteration, update the maxIndexReach so it contains the maximum position one could reach from the current index i as max of maxIndexReachand i + nums[i](addition of current position and from the current position maximum jump value).
  5. During iteration, if current array index position i > currentIndexReach, it means that we are ready for another jump as we have already crossed the last max jump position. Increment maxJumps by 1 and assign currentIndexReach to the current maximum position, which is maxIndexReach. At this point if the currentIndexReach is equal to our destination index which is the last index we can return the no of jumps as an answer.
  6. Return the number of jumps when the loop exits.

Time complexity

The time complexity will be O(n) because we iterate the array only once.

Space complexity

The space complexity will be O(1) because constant space is utilized.

--

--

--

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

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Higher Order Functions in Swift

XCUITest — Test Automation Organization

Create a Circular Loading using swiftUI

How to use Apple’s Grand Central Dispatch library to multitask threads like a Pro!

XCTests: Actually Writing Them

Airbnb’s Page Performance Score on iOS

How to Build a Simple iOS Home Screen PWA Camera Using Vue, Tailwind, and WebRTC on CodePen

iOS 14.3 Brings WebRTC to WKWebView, Closing Gap on iOS Accessibility

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jaydeep

Jaydeep

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

More from Medium

Swap Nodes in Pairs

Validate Binary Search Tree

35. Search Insert Position

Conclusion