5-line C++ greedy solution (detailed explanation)


  • 0

    Key observation: by definition, all reachable indices must be consecutive, so the further you could jump with fixed number of steps, the fewer jumps it takes to reach the end.

    Suppose you are currently at some value nums[cur], the furthest reachable is index max_reach = cur+nums[cur]. So which one to land between index range (cur, max_reach]? Well, pick the one to maximum the total distance after next jump, i.e., land to index next which maximizes next+nums[next] for next in (cur, max_reach].

        int jump(vector<int>& nums) {
            int cur = 0, res = 0, max_reach;
            while (cur < nums.size()-1 && ++res) {
                if ((max_reach = cur+nums[cur]) >= nums.size()-1) return res;
                for (int i = ++cur; i <= max_reach; ++i) if (i+nums[i] > cur+nums[cur]) cur = i;
            }
            return res;
        }
    

Log in to reply
 

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