Today I have done leetcode's February LeetCoding Challenge with cpp.

February LeetCoding Challenge 8

Description

Jump Game II

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

• 0 <= j <= nums[i] and
• i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [2,3,0,1,4]
Output: 2

Constraints:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 1000

Solution

class Solution {
public:
  int jump(vector<int>& nums) {
    int len = nums.size();
    queue<pair<int, int>> q;
    q.push({0, nums[0]});
    nums[0] = -1;
    int answer = 0;
    while(q.size()) {
      int sz = q.size();
      // cout << "round " << answer << ": " << endl;
      for(int i = 0; i < sz; ++i) {
        auto [index, offset] = q.front();
        // cout << index << ' ' << offset << endl;
        if(index == len - 1) return answer;
        q.pop();
        for(int j = max(0, index - offset); j < min(len, index + offset + 1); ++j) {
          if(nums[j] < 0) continue;
          q.push({j, nums[j]});
          nums[j] = - 1;
        }
      }
      // cout << endl;
      answer += 1;
    }
    return -1;
  }
};

// Accepted
// 109/109 cases passed (356 ms)
// Your runtime beats 32.61 % of cpp submissions
// Your memory usage beats 15.91 % of cpp submissions (17.7 MB)