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


  • 0
    W

    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;
        }
    };
    

Log in to reply
 

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