educative.io

Time Coplexity: Tell me the time coplexity and check if its better than provided solution

Courses
,
#1 
let find_subarrays = function(arr, target) {
let result = [],
  // TODO: Write your code here
  q = [],
  curProd = 1;
  // windowStart = 0;


for(let windowEnd=0; windowEnd<arr.length; windowEnd++){
  let rightNum = arr[windowEnd];
    q.push(rightNum); 
    curProd *= rightNum;

  while(curProd>=target && q.length !== 0){
    let exitNum = q.shift();
    curProd = curProd / exitNum;
  }

  if(rightNum < target){
    result.push([rightNum])
  }

  if(curProd < target){
    if(q.length > 1){
      result.push(q.slice());
    }
  }
}

return result;
};
#2

Hi @Shubham_Prakash,

The time complexity of the solution you provided will be O(n^3) which is similar to the solution provided in the lesson.

Your solution has time complexity O(n^3) because the q.shift() function has a time complexity of O(n), combined with the for and the while loops it becomes an overall average time complexity of O(n^3). The solution you have provided is correct however and it gets the job done so in the end it is similar to the one provided in the course with regards to the time complexity.

1 Like