🎙 Free live masterclass · Sun, 29 Nov, 7:00 pm IST · Java Full Stack roadmap Register free →
Skills101
← Quiz: Monotonic Stack: all 13 questions

Quiz: Monotonic Stack · Question 3 of 13

Why is the monotonic stack solution O(n) even with a while loop inside a for loop?

Why is the monotonic stack solution O(n) even with a while loop inside a for loop?

  1. A.The while loop runs at most once per step
  2. B.Each index is pushed once and popped at most once, so all the while loops together run at most n times
  3. C.Python optimises nested loops
  4. D.It isn't — it is O(n²)
Answer & explanation

Correct answer: Each index is pushed once and popped at most once, so all the while loops together run at most n times

Count the total work: n pushes and at most n pops.

Can you get the rest right without peeking?

Take the timed Quiz: Monotonic Stack quiz free. Pass it to earn XP and count towards your certificate.

Start the quiz →