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