CODEWITHSUNDEEP
javascriptarraysdata-structures
Shivam Gupta
Shivam Gupta

Reputation: 159

Time complexity of Monotonic stack question

As I understand , the time complexity of this code is O(N) The for loop will iterate just once , so the time complexity accounts for O(N) but there is a while loop inside the for loop

So there is a while loop nested inside the for loop Why are we ignoring the time complexity of that?

var dailyTemperatures = function(temperatures) {
    let result = new Array(temperatures.length).fill(0);
    let stack = [];

    for(let i = 0; i < temperatures.length; i++) {
        while(stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
            let index = stack.pop();
            console.log('hello');
            result[index] = i - index;
        }
        stack.push(i);
    }
    return result;
};

Upvotes: 2

Views: 989

Answers (2)

himanshu sharma
himanshu sharma

Reputation: 11

It becomes confusing if you look at it like nested loops. The approach in monotonic stack is that every element is pushed once into the stack and popped once too. So for every element there will be max 2 operations. Thus it becomes 2 * O(n) , which translates loosely to O(n).

Upvotes: 1

Vishal
Vishal

Reputation: 706

Because while loop is simply poping stack elements one by one and there can not be more than N elements pushed inside the stack ( every element pushed once ). So even though while loop is nested inside for loop it will not execute more that N times.

Upvotes: 2

Related Questions