0
$\begingroup$

I'm practicing leet code questions and want to understand more fully how to determine Big O notation. What is the algorithmic complexity of my solution to the following problem?

O(n^2) ? For every item in n I could loop an additional n[i] times. Or is it O(n) ?

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Input: [2,3,1,1,4]

Output: true

Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

var canJump = function(nums) {

  let validIndices = {};
  for(let i = nums.length - 1; i >= 0; i--) {
    let currentNum = nums[i]; 
    if(currentNum + i >= nums.length - 1) {
      validIndices[i] = true;
    } else {
      while(currentNum > 0) {
        if(validIndices[i + currentNum]) {
          validIndices[i] = true;
        }
        currentNum--;
      }
    }
  }

  return !!validIndices[0];
};
$\endgroup$
1
$\begingroup$

Your algorithm has O(n^2) worst case complexity. You have a for loop of O(n). Inside your for loop you have a while loop which is O(currentNum). So if your currentNum is O(n) (ex nums[i] = length.nums for each i) then the complexity is O(n*n) = O(n^2).

Hint

Try not to recalculate things. You could use Dynamic programming technique. You need:

def canJump(i):
    if valid[i] has been assigned a True or False value:
        return valid[i]
    #else calculate valid[i]
    if i + nums[i] > len(nums):
        valid[i] = True
        return valid[i]
    for jump in range(1, len(nums[i])):
        valid[i] = any(False, canJump(i + jump))
    return valid[i]

print(canJump(0))

This is just a pseudocode. I have not tried it. This way you only visit an element of nums once so it’s O(n).

[EDIT]
Actually I am wrong. My code is also O(n^2). Here is an O(n) solution.

at_least = n 
for i from n-1 to 0:
    if nums[i] + i >= at_least:
        at_least = i 
if at_least == 0: True else False

Now I think this is right. Sorry for the confusion. I got confused too.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.