Why time limit on all '1' case


  • 0
    Z
    int jump(vector<int>& nums) {
    
    //step[i] stores the min step from index 0 to each i
    vector<int> step = vector<int>(nums.size()+1, 0x7ffffff);
    step[0] = 0;
    for (int index = 1; index <= nums.size(); index++) {
      for (int s = 0; s < index; s++) {
         if (nums[s] + s >= index){
           step[index] = min(step[s]+1, step[index]);
         }
      }
    }
    //return the min step when reach nums.size()
    return step[nums.size()];
    }

  • 0
    F

    when it's all 1, the time complexity is O(n^2), because two nested for loop.


Log in to reply
 

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