Possibly the simplest O(n) solution with explanation (9 lines in C++)

• My solution is based on the observation that if you can reach index `i`, then you are always able to reach index `i - 1` too (proof: think of the last jump taken to reach index `i`. If it was of length `1`, then you were already at index `i - 1`. If it was of length `>= 2`, then you could have taken a 1-unit smaller jump to land on `i -1` instead of `i`). Furthermore, following the same reasoning, if you can reach index `i` in `w` jumps, you can also reach index `i-1` using no more than `w` jumps (but perhaps even less).

Let `reach[i]` be the farthest you can reach in the next jump assuming you are able to reach index `i`. (Remember, if you can reach in `i` in `w` jumps, then you can also reach any smaller index in no more than `w` jumps). Therefore, `reach[i]` is simply `max(k + nums[k])` for all `k` with `0 <= k <= i`).

You can precompute `reach[i]` in O(n) for all `i`'s. (Note that in my code I reuse `nums` to precompute it and avoid defining a new array to save some memory.)

After that you just simulate the jumps, always reaching as far as you can until you reach the end.

``````class Solution {
public:
int jump(vector<int>& nums) {
int n = nums.size();
for (int i = 1; i < n; ++i) {
nums[i] = max(nums[i - 1], i + nums[i]);
}
int jumps = 0;
for (int at = 0; at < n - 1; at = nums[at]) {
jumps++;
}
return jumps;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.