DSA sheet · Stack · Monotonic stack pattern

Next Greater Element

This is the first problem of the stack topic and the first problem of the monotonic stack pattern. The teacher first writes the obvious two-loop answer, shows why it is too slow for the given limits, and then builds the stack answer step by step. If you understand why we pop and what the stack is remembering on this page, the next problems (circular array, daily temperatures, histogram…) become small changes of the same idea.

At the end she also explains how the LeetCode version (496, with two arrays nums1 and nums2) is just this same function plus a lookup.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Stacks from scratch + what a monotonic stack is
• Part A · Brute force: two loops
• Part B · Optimal: monotonic stack from the right
• Part C · LeetCode 496 version (nums1 inside nums2)
• Part D · Revision page

Part 0 · Before starting

What is a stack?

A stack is a pile of items where you can only touch the top. Think of a pile of plates: you put a new plate on top, and you take a plate from the top. You never pull a plate out from the middle.

This rule has a name: LIFO = Last In, First Out. The item that went in last is the first one to come out.

Unlike an array, a stack gives you no indexing: you can't ask for "the 3rd item". You only get three actions:

In this notebook, a stack is always drawn left = bottom, right = top, like [4, 3, 1] where 1 is on top. In the vertical pictures, the top is at the top, drawn in red.

Why do we need a stack at all?

Many array problems ask, for each position, "what is the first bigger (or smaller) item after me?" or "before me?". The simple way is a second loop that walks forward or backward from every position. Two loops over n items cost about n² steps.

A stack lets us remember the useful items we've already passed, so we never walk back over them. That turns n² into n.

What is a monotonic stack?

Monotonic means "always going one way". A monotonic stack is a normal stack where we keep the items in sorted order from bottom to top, either always decreasing or always increasing.

How do we keep it sorted? Before pushing a new item, we pop every item on top that would break the order. In this problem:

• We want the next greater item, so we pop every top item that is smaller than or equal to the new item.
• After the pops, the stack (bottom → top) is strictly decreasing: the biggest at the bottom, the smallest on top.

What does the stack remember? Only the items that can still be an answer for someone in the future. Every item we pop is one we have proved can never be an answer again (Part B, step 4 explains the proof). That is the whole trick.

Part A · Brute force: two loops

GFG "Next Greater Element" (also the core of LeetCode 496)

1The question in simple words

You get an array. For every element, find the next greater element: the first element to its right that is strictly bigger than it. If no such element exists, write −1.

• For 1: 3, 2 and 4 are all bigger. But "next" means the nearest one, the first one we meet going right → 3.
• For 3: 2 is smaller, skip it. 4 is bigger → 4.
• For 2: the next item 4 is bigger → 4.
• For 4: nothing to its right at all → −1.

"Greater" means strictly greater. An equal value doesn't count: for [3, 3], the first 3 gets −1, not 3.

2What the constraints tell us

• Array size can be up to 10⁶. That's huge.
• The teacher's rule of thumb: roughly 10⁸ simple steps fit in the time limit. Beyond that it's risky, and around 10⁹ you'll surely get TLE (Time Limit Exceeded).
• An O(n²) solution would do about (10⁶)² = 10¹² steps → definitely TLE. So the brute force below is only a starting point for understanding. We must reach O(n).

3Intuition

Stand on one element with your left finger (i). Walk your right finger (j) to the right, one step at a time, and stop at the first bigger value. Write that value down for i. Then move i one step and start over.

4Building the logic, the way the teacher does

5Approach steps

1. Make ans of size n filled with −1.
2. For each i from 0 to n − 2:
3. For each j from i + 1 to n − 1: if arr[j] > arr[i], set ans[i] = arr[j] and break.
4. Return ans.

6Code (Python)

class Solution:
    def nextLargerElement(self, arr):
        n = len(arr)
        ans = [-1] * n                      # default: no greater element
        for i in range(n - 1):              # last index keeps -1
            for j in range(i + 1, n):       # look only to the right
                if arr[j] > arr[i]:         # strictly greater
                    ans[i] = arr[j]
                    break                   # first one found = the "next" one
        return ans

The teacher's Java version returns an ArrayList, so she adds values to it instead of using indexes. In Python we simply make a list of the right size and assign by index.

7Code line by line

8Dry run on [1, 3, 2, 4]

9Complexity & remember

The break helps sometimes, but think about the worst case: a decreasing array like 9 8 7 6 5 4 3 2 1. Nobody has a bigger item on the right, so j never breaks early. For 9 it scans 8 items, for 8 it scans 7, and so on. Total ≈ n·(n−1)/2 → O(n²).

• Time O(n²): with n = 10⁶ that's about 10¹² steps → TLE (the teacher submits it and it does TLE).
• Space O(1) extra (besides the answer list).

Part B · Optimal: monotonic stack from the right

1The question again, with a new goal

Same question, same answer. Now we want one loop instead of two, so the cost drops from O(n²) to O(n).

2What the constraints tell us

• n up to 10⁶ → O(n) means about 10⁶ steps (a few million with the pops). That's very safe.
• We may use O(n) extra space for the stack. Here that's allowed, and it's the price we pay for the speed.

3Intuition: walk from the right and keep a "skyline"

The answer for an element depends on what lies to its right. If we walk left to right, we haven't seen the right side yet, so we'd have to scan forward again. That's the brute force.

So the teacher flips the direction: start from the last index and walk left. When we reach index i, every element to its right has already been seen. We just need to keep a short summary of them. That summary is the stack.

Picture standing at i and looking right at a row of buildings. A short building hidden behind a taller one closer to you can never be "the first taller one" for you or anyone further left. Only the visible skyline matters, and the stack is that skyline: nearest building on top, getting taller as you go down.

For the last element there's nothing on the right, so its answer is −1. That's why the answer list is pre-filled with −1 again.

4Building the logic from the example

Array [1, 3, 2, 4], walking from the right.

At 4 (index 3)

The stack is empty, so there's nothing on the right → answer −1. Now push 4: it might be the answer for someone on the left. Stack: [4].

At 2 (index 2)

The stack is not empty, so look at the top: 4. Is 4 bigger than 2? Yes. So 4 is the answer for 2. We don't need to look any deeper into the stack: the top is the nearest remaining candidate, so if it's bigger, it's the first bigger one.

Then push 2. Even though 2 is small, it could still be the answer for some smaller element further left (for example a 0). Stack: [4, 2].

At 3 (index 1): the first pop

Top is 2. Is 2 bigger than 3? No. So 2 is not the answer for 3. The teacher gives two reasons to pop 2 (throw it away) instead of just skipping it:

1. It's useless for 3, and popping it is O(1). We look at the next item without walking back through the array.
2. It's useless for everyone to the left of 3 too. Take any future element z on the left. If 2 were bigger than z, then 3 is also bigger than z (because 3 > 2), and 3 is closer to z. So 3 would be found first, never 2. In skyline words: 2 is now hidden behind 3.

After popping 2, the top is 4. Is 4 bigger than 3? Yes → answer for 3 is 4. Push 3. Stack: [4, 3].

At 1 (index 0)

Top is 3, and 3 > 1 → answer 3, no pop. Push 1. Stack: [4, 3, 1]. Final answer [3, 4, 4, −1] ✓.

The equal case: why pop when top == current?

The teacher changes the example to show this. Suppose the array were [3, 1, 3, 2, 4], so there's another 3 left of the 1. When we reach that left 3, the stack is [4, 3, 1]:

• Top 1: not bigger than 3 → pop.
• Top 3: equal. "Next greater" needs strictly greater, so this 3 is not the answer → pop it too. It's also hidden from now on: the new 3 is just as tall and closer.
• Top 4: bigger → answer is 4.

So the pop condition is top <= current, not top < current.

What the stack holds, in one sentence

At any moment, the stack holds, from top to bottom, the elements to the right of i that are not hidden by a closer element that's at least as tall. Their values are strictly increasing from top to bottom. The top is always the nearest candidate.

5Approach steps

1. Make ans of size n filled with −1, and an empty stack.
2. For i from n − 1 down to 0, with x = arr[i]:
3. While the stack is not empty and its top ≤ x → pop (the top is hidden forever).
4. If the stack is still not empty → ans[i] = top.
5. Push x.
6. Return ans.

6Code (Python)

class Solution:
    def nextLargerElement(self, arr):
        n = len(arr)
        ans = [-1] * n
        st = []                              # values; bottom -> top is strictly decreasing
        for i in range(n - 1, -1, -1):       # walk from the RIGHT end
            x = arr[i]
            while st and st[-1] <= x:        # top is not greater -> useless forever
                st.pop()
            if st:                           # whatever is left on top is the answer
                ans[i] = st[-1]
            st.append(x)                     # x is the nearest candidate for the left side
        return ans

7Code line by line

8Dry run

Example 1: [1, 3, 2, 4]

Read each picture bottom to top: the values always decrease going up. That's the "monotonic" part.

Example 2 (the equal case): [3, 1, 3, 2, 4]

9Complexity & remember

It looks like a loop inside a loop, so you might guess O(n²). The teacher explains why it's actually about 2n:

• The for loop runs n times, once per element. It never restarts.
• The while loop only pops. Every element is pushed exactly once, so it can be popped at most once. Once popped, it never comes back into the stack.
• So across the whole run, the while loop pops at most n times in total, not n times per element. Take 4 3 2 1 walked from the right: 1 is pushed; 2 pops 1; 3 pops 2; 4 pops 3. That's three pops in total.

Time O(n + n) = O(2n) = O(n). Space O(n) for the stack (worst case an increasing array, where nothing is ever popped, e.g. 1 2 3 4 from the right leaves [4, 3, 2, 1]).

The 4 standard variants (same code, two knobs)

Knob 1: walk from the side where the answer lives. Knob 2: pop everything that is "not good enough" to be the answer.

Part C · LeetCode 496 version (nums1 inside nums2)

LeetCode 496. The teacher explains this version at the end of the video but doesn't code it. The code below is that explanation written out.

1The question in simple words

You get two arrays. nums2 is the real array. nums1 is a list of some values picked from nums2. All values are different. For each value in nums1, find where it sits in nums2 and return its next greater element in nums2 (or −1).

2What the constraints tell us

• Lengths up to 1000, so even O(n²) would pass here. But the O(n) way is just as short.
• All values are unique → we can use the value itself as a dictionary key (value → its next greater).

3Intuition

Step 1: run the normal next-greater function on nums2. Step 2: answer each query in nums1 by looking it up. The only new piece is the dictionary that connects a value to its answer.

4Building the logic

5Approach steps

1. Walk nums2 from the right with the Part B stack. For each value x, store nge[x] = the top (or −1).
2. Return [nge[x] for x in nums1].

6Code (Python)

class Solution:
    def nextGreaterElement(self, nums1, nums2):
        nge = {}                             # value -> its next greater in nums2
        st = []
        for x in reversed(nums2):            # same walk as Part B, from the right
            while st and st[-1] <= x:
                st.pop()
            nge[x] = st[-1] if st else -1
            st.append(x)
        return [nge[x] for x in nums1]       # answer each query by lookup

7Code line by line

8Dry run (nums2 = [1, 3, 4, 2])

Queries [4, 1, 2] → [−1, 3, −1] ✓

9Complexity & remember

• Time O(n + m): n for the stack walk over nums2, m for the lookups.
• Space O(n): the stack and the dict.

Part D · Revision page

s = Solution()
print(s.nextLargerElement([1, 3, 2, 4]))       # [3, 4, 4, -1]
print(s.nextLargerElement([3, 1, 3, 2, 4]))    # [4, 3, 4, 4, -1]
print(s.nextLargerElement([4, 3, 2, 1]))       # [-1, -1, -1, -1]
print(s.nextLargerElement([5, 5, 5]))          # [-1, -1, -1]
print(s.nextLargerElement([7]))                # [-1]

Based on this video: Next Greater Element | Monotonic Stack