Grokking 75: Top Coding Interview Questions
Vote

0% completed

​

Introduction to Monotonic Stack

You are given the daily temperatures for a week. For each day, say how many days you must wait before it gets warmer.

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

The direct approach takes each day and scans forward until it finds a warmer one. In the worst case, a list that only ever gets colder, every scan runs to the end. That is O(N²).

Now watch what happens on the day it reaches 72. Three days are still waiting for an answer: 75, 71 and 69. The 72 answers 71 and 69 at the same time, and it answers nothing else, because 75 is still larger.

.....

.....

.....

Like the course? Get enrolled and start learning!
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
Kinshuk Agrawal

Kinshuk Agrawal

· 2 years ago

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

A

Anand Mohan

· 3 years ago

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