Leetcode 45 Solution

This article provides solution to leetcode question 45 (jump-game-ii)
Categories:
Tags:
Access this page by simply typing in "lcs 45" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/jump-game-ii

Solution

class Solution {
public:
    int jump(vector<int>& nums) {
        int start = 0;
        int end = 0;
        int count = 0;
        int max_pos = 0;



        if (nums.size() == 1)
            return 0;



        while (end < nums.size())
        {
            count++;



            for (int i = start; i <= end; i++)
            {
                if (i + nums[i] >= nums.size() - 1)
                    return count;



                max_pos = max(max_pos, i + nums[i]);
            }



            start = end + 1;
            end = max_pos;
        }



        return count;
    }
};