O(n²) vs O(n): Stack Saves the Day
45sContrasts a naive trillion-step solution with a clever linear-time stack approach, sparking curiosity about algorithm optimization.
▶ Play ClipAI Summary
This video explains how to solve the 'Daily Temperatures' coding interview problem efficiently. It demonstrates a monotonic stack approach that reduces the time complexity from O(N^2) to O(N), making it suitable for large inputs like a million days.
Chapters
[00:01]
Problem Definition
Given daily temperatures, for each day, count how many days until the next warmer day.
[00:14]
Naive Solution and Its Flaw
The naive approach scans forward for each day, resulting in O(N^2) time complexity, which is impractical for large inputs (e.g., a million days would take a trillion operations).
[00:26]
Monotonic Stack Approach
Use a stack of indices for days still waiting for a warmer day. When a warmer day appears, pop all colder days from the stack and record the gap for each.
[00:39]
Trace Example
First three days get cooler, so their indices are pushed onto the stack (0,1,2). When 72 appears, it's warmer than 69 (index 2), so pop and record 1. Then it's warmer than 71 (index 1), pop and record 2.
[01:05]
Complexity Analysis
Each index is pushed and popped once, so the algorithm runs in O(N) time, collapsing the O(N^2) scan into a single linear sweep.
[01:18]
Key Takeaway
When you need to find the next greater element to the right, use a monotonic stack.
The monotonic stack technique is a powerful optimization for problems involving next greater elements, reducing time complexity from quadratic to linear.
Mentioned in this Video
Tutorial Checklist
2
00:39
Iterate through each day's temperature. While the stack is not empty and the current temperature is warmer than the temperature at the index on top of the stack, pop the index and record the difference (current index - popped index) as the answer for that day.
4
01:05
After the loop, any remaining indices in the stack have no warmer day ahead; their answer is 0.
Study Flashcards (5)
What is the naive time complexity for the Daily Temperatures problem?
easy
Click to reveal answer
What is the naive time complexity for the Daily Temperatures problem?
easy
Click to reveal answer
O(N^2)
00:14
What data structure is used to optimize the solution?
easy
Click to reveal answer
What data structure is used to optimize the solution?
easy
Click to reveal answer
A monotonic stack
00:26
In the example, what is the answer for day index 1 (temperature 71)?
medium
Click to reveal answer
In the example, what is the answer for day index 1 (temperature 71)?
medium
Click to reveal answer
2
00:52
What is the time complexity of the optimized solution?
easy
Click to reveal answer
What is the time complexity of the optimized solution?
easy
Click to reveal answer
O(N)
01:05
What is the key takeaway for problems involving next greater elements?
medium
Click to reveal answer
What is the key takeaway for problems involving next greater elements?
medium
Click to reveal answer
Use a monotonic stack.
01:18
💡 Key Takeaways
🔧
Monotonic Stack Insight
Introduces the core optimization technique that turns a quadratic solution into a linear one.
00:26
📊
Linear Time Complexity
Demonstrates that each element is processed only twice, leading to O(N) performance.
01:05
⚖️
General Principle
Provides a reusable rule for solving similar problems, making it a valuable interview tip.
01:18Full Transcript
[00:01] daily temperatures and asks, "For each day, count how many days until the next Now, your instinct might be to pick each day and then just scan forward until a warmer day appears. That does work, but then they say that the input is maybe a
[00:14] million days, and that O of N squared solution is going to take a trillion See, you can actually do this in a single pass. All you need is a stack of indices for the days still waiting on a warmer
[00:26] So, when a warmer day does show up, every colder day on the stack just found its answer. You now know exactly how long each one waited. So, you pop them off and you record the gap for each. Let's quickly trace it on an example.
[00:39] The first three days only get cooler, so each one pushes its index and waits. The each one pushes its index and waits. The stack now holds 0, 1, and 2, decreasing from bottom to top. 72 is warmer than the 69 on top. So, you
[00:52] 1. It's still warmer than the 71 now on It's still warmer than the 71 now on top, so pop index 1 and record 3 - 1, which is 2. One warmer day just cleared two waiting days.
[01:05] Every index gets pushed once and popped once, so that previous O of N squared scan now collapses into one linear sweep. element to the right, reach for a monotonic stack.
[01:18] Follow us for more coding interview breakdowns at hellointerview.com.
