Solution to Jump Game II by LeetCode

2 Replies to “Solution to Jump Game II by LeetCode”

1. Your solution is O(N^2) in the worst case? [1,5,4,3,2,1,1,1]

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

   #include <vector> using namespace std; class Solution { public:     int jump(vector<int>& nums) {         int len = nums.size() - 1;         int ans = 0, currentMaxPos = 0, nextMaxPos = 0;         for(int i = 0; i < len; ++i)         {             if(i + nums[i] >= len)                 return ++ans;             nextMaxPos = std::max(nextMaxPos, i + nums[i]);             if(currentMaxPos == i)             {                 if(nextMaxPos == currentMaxPos)                     return 0;                 ++ans;                 currentMaxPos = nextMaxPos;             }         }         return ans;     } };

   Reply

   • Yes, I think so. The time complexity of my solution is much worse than yours.

     Reply