Interview Bootcamp
Vote

0% completed

​

Introduction to Monotonic Stack

You are given a list of daily temperatures. For each day, find how many days you must wait for a warmer temperature.

[73, 74, 75, 71, 69, 72, 76]

A simple solution starts at every day and scans forward until it finds a warmer day.

In the worst case, each scan reaches the end of the list. This gives O(N²) time.

We can avoid repeating these scans by keeping only the days that are still waiting for an answer.

When temperature 72 arrives, it answers the days with temperatures 71 and 69. It does not answer the day with 75.

.....

.....

.....

Like the course? Get enrolled and start learning!
Kinshuk Agrawal

Kinshuk Agrawal

· 3 years ago

It would be nice to have such a comprehensive explanation + pseudo code for every pattern

K

karrad

· 3 years ago

  • Input: nums1 = [9,7,1], nums2 = [1,7,9,5,4,3]
  • Output: [-1,9,7]

In this example, we first take 9 and compare to every number to right of 9 in nums2. No number >9 so -1

Then 7. The 1st number to right of 7 (i.e only consider last 4 numbers in nums2) is 9

Now we consider 1. If we go by the same logic, we should only consider 5,4,3 in nums2. Why is the answer 7? Should it not be 5?

Thanks

M

Show 2 replies
A

Anand Mohan

· 3 years ago

There seems to be a mistake in the image. We are using monotonically decreasing stack.

Reading Progress

0%

Vote for new content