Introduction

Among all the problems built around the Stack data structure, four stand out as a family — they appear repeatedly in coding interviews, competitive programming, and real-world software systems. These four are the Next Greater to the Right (NGR), Next Greater to the Left (NGL), Next Smaller to the Right (NSR), and Next Smaller to the Left (NSL).

What makes them special is not just their individual solutions — it is the fact that all four are solved by a single elegant technique called the Monotonic Stack. Learn the pattern once, and you have all four in your toolkit permanently.

This guide breaks down each problem with a full solution, step-by-step dry run, edge cases, and the exact reasoning behind every decision in the code. Whether you are preparing for a technical interview or simply want to deeply understand this pattern — you are in the right place.

The Story That Makes This Click

Before any code, let us understand this family of problems with one real-world story.

Imagine you are standing in a queue at a cricket stadium. Everyone in the queue has a different height. You are standing somewhere in the middle. You look to your right and ask — who is the first person taller than me? That is your Next Greater Element to the Right (NGR).

Now you look to your left — who is the first person taller than me on this side? That is your Next Greater to the Left (NGL).

Now instead of taller, you ask shorter — who is the first shorter person to my right? That is Next Smaller to the Right (NSR).

And shorter to your left? That is Next Smaller to the Left (NSL).

Same queue. Same people. Four different questions. Four different answers. This is exactly what these four problems are about — and they all share the same solution pattern.

What Is a Monotonic Stack?

A monotonic stack is just a regular stack with one rule — elements inside it are always maintained in a specific order, either always increasing or always decreasing from bottom to top.

You never enforce this rule explicitly. It happens naturally as you pop elements that violate the order before pushing a new one. This popping step is the key insight — the moment you pop an element, you have found its answer for the current element being processed.

This one pattern solves all four problems. Only two small details change between them — the direction of traversal and the comparison condition inside the while loop.

The Four Problems — Quick Reference

Problem 1 — Next Greater Element to Right (NGR)

GFG Problem: Search "Next Greater Element" on GeeksForGeeks Difficulty: Medium | Accuracy: 32.95% | Submissions: 515K+

The Question

For each element in the array, find the first element to its right that is strictly greater than it. If none exists, return -1.

Input: [1, 3, 2, 4] Output: [3, 4, 4, -1]

Input: [6, 8, 0, 1, 3] Output: [8, -1, 1, 3, -1]

Real World Example

Think of the stock market. You have daily closing prices: [1, 3, 2, 4]. For each day, you want to know — on which future day will the price first exceed today's price? Day 1 has price 1, first exceeded on Day 2 with price 3. Day 2 has price 3, first exceeded on Day 4 with price 4. Day 3 has price 2, also first exceeded on Day 4 with price 4. Day 4 has no future day, so -1. This is exactly NGR — and it is literally used in financial software to detect price breakout points.

The Intuition

The brute force is obvious — for every element, scan everything to its right and find the first greater one. That works but it is O(n²). For an array of 10⁶ elements that becomes 10¹² operations. It will time out on any large input.

The stack insight is this — traverse right to left. As you move left, the stack always holds elements you have already seen on the right side. These are the candidates for being the next greater element. Before pushing the current element, pop all stack elements that are smaller than or equal to it. Why? Because the current element is blocking them — for any future element to the left, the current element will always be encountered first, so those smaller popped elements can never be an answer for anything. Whatever remains on top of the stack after popping is the answer for the current element.

Step-by-Step Dry Run

Array: [1, 3, 2, 4], traversing right to left.

i=3, element is 4. Stack is empty. Answer for index 3 is -1. Push 4. Stack: [4]

i=2, element is 2. Top of stack is 4, which is greater than 2. Answer for index 2 is 4. Push 2. Stack: [4, 2]

i=1, element is 3. Top of stack is 2, which is not greater than 3. Pop 2. Top is now 4, which is greater than 3. Answer for index 1 is 4. Push 3. Stack: [4, 3]

i=0, element is 1. Top of stack is 3, which is greater than 1. Answer for index 0 is 3. Push 1. Stack: [4, 3, 1]

Answers collected right to left: [-1, 4, 4, 3] After Collections.reverse(): [3, 4, 4, -1] ✓

The Code

Edge Cases

1. All elements decreasing — Input: [5, 4, 3, 2, 1] Output: [-1, -1, -1, -1, -1] Every element has no greater element to its right. Traversing right to left, each new element is larger than everything already in the stack, so the stack gets cleared and the answer is always -1.
2. All elements increasing — Input: [1, 2, 3, 4, 5] Output: [2, 3, 4, 5, -1] Each element's next greater is simply the next element in the array. The last element always gets -1 since nothing exists to its right.
3. All elements equal — Input: [3, 3, 3, 3] Output: [-1, -1, -1, -1] Equal elements do not count as greater. The pop condition uses >= so equals get removed from the stack, ensuring duplicates never answer each other.
4. Single element — Input: [7] Output: [-1] Nothing to the right, always -1.

Why only 32.95% accuracy on GFG? Most people either forget to reverse the result at the end, use the wrong comparison in the while loop, or submit a brute force O(n²) solution that times out on large inputs.

Problem 2 — Next Greater Element to Left / Previous Greater Element (NGL)

GFG Problem: Search "Previous Greater Element" on GeeksForGeeks Difficulty: Medium | Accuracy: 68.93% | Submissions: 7K+

The Question

For each element in the array, find the first element to its left that is strictly greater than it. If none exists, return -1.

Input: [10, 4, 2, 20, 40, 12, 30] Output: [-1, 10, 4, -1, -1, 40, 40]

Real World Example

Imagine you are a junior employee at a company. For each person in the office, you want to know — who is the first senior person sitting to their left who earns more? This is NGL. It is used in organizational hierarchy systems, salary band analysis tools, and even in database query optimizers to find the nearest dominant record on the left side.

The Intuition

This is the mirror image of NGR. Instead of traversing right to left, we traverse left to right. The stack holds elements we have already seen from the left side — these are candidates for being the previous greater element. For each new element, pop everything from the stack that is smaller than or equal to it. Whatever remains on top is the first greater element to its left. Then push the current element for future use.

No reverse is needed here because we are already going left to right and building the result in order.

Step-by-Step Dry Run

Array: [10, 4, 2, 20, 40, 12, 30], traversing left to right.

i=0, element is 10. Stack is empty. Answer is -1. Push 10. Stack: [10]

i=1, element is 4. Top is 10, greater than 4. Answer is 10. Push 4. Stack: [10, 4]

i=2, element is 2. Top is 4, greater than 2. Answer is 4. Push 2. Stack: [10, 4, 2]

i=3, element is 20. Top is 2, not greater than 20. Pop 2. Top is 4, not greater. Pop 4. Top is 10, not greater. Pop 10. Stack is empty. Answer is -1. Push 20. Stack: [20]

i=4, element is 40. Top is 20, not greater. Pop 20. Stack empty. Answer is -1. Push 40. Stack: [40]

i=5, element is 12. Top is 40, greater than 12. Answer is 40. Push 12. Stack: [40, 12]

i=6, element is 30. Top is 12, not greater than 30. Pop 12. Top is 40, greater than 30. Answer is 40. Push 30. Stack: [40, 30]

Result: [-1, 10, 4, -1, -1, 40, 40] ✓ No reverse needed.

The Code

Edge Cases

1. Strictly increasing array — Input: [10, 20, 30, 40] Output: [-1, -1, -1, -1] Each new element is larger than everything before it, so the stack always gets fully cleared. No previous greater exists for any element.
2. First element is always -1 — regardless of its value, the first element has nothing to its left. The stack is empty at i=0, so the answer is always -1 for index 0. This is guaranteed by the logic.
3. Duplicate values — Input: [5, 5, 5] Output: [-1, -1, -1] Equal elements do not qualify as greater. The pop condition uses >= so duplicates get removed from the stack and never answer each other.

Problem 3 — Next Smaller Element to Right (NSR)

GFG Problem: Search "Next Smaller Element" on GeeksForGeeks Difficulty: Medium | Accuracy: 36.26% | Submissions: 225K+

The Question

For each element in the array, find the first element to its right that is strictly smaller than it. If none exists, return -1.

Input: [4, 8, 5, 2, 25] Output: [2, 5, 2, -1, -1]

Input: [13, 7, 6, 12] Output: [7, 6, -1, -1]

Real World Example

You work at a warehouse. Shelves have items of weights: [4, 8, 5, 2, 25] kg. For each item, the system needs to find the first lighter item sitting to its right on the shelf — this is used to optimize load balancing and shelf arrangement algorithms. Item of 4 kg — first lighter to the right is 2 kg. Item of 8 kg — first lighter is 5 kg. Item of 5 kg — first lighter is 2 kg. Items of 2 kg and 25 kg have no lighter item to their right, so -1.

The Intuition

NSR is structurally identical to NGR — we traverse right to left and collect answers, then reverse. The only change is the pop condition. In NGR we popped elements smaller than or equal to current because we wanted greater. Here we want smaller, so we pop elements greater than or equal to current. After popping, whatever remains on top is the first smaller element to the right.

Step-by-Step Dry Run

Array: [4, 8, 5, 2, 25], traversing right to left.

i=4, element is 25. Stack is empty. Answer is -1. Push 25. Stack: [25]

i=3, element is 2. Top is 25, which is greater than or equal to 2. Pop 25. Stack is empty. Answer is -1. Push 2. Stack: [2]

i=2, element is 5. Top is 2, which is less than 5. Answer is 2. Push 5. Stack: [2, 5]

i=1, element is 8. Top is 5, which is less than 8. Answer is 5. Push 8. Stack: [2, 5, 8]

i=0, element is 4. Top is 8, which is greater than or equal to 4. Pop 8. Top is 5, which is greater than or equal to 4. Pop 5. Top is 2, which is less than 4. Answer is 2. Push 4. Stack: [2, 4]

Answers collected right to left: [-1, -1, 2, 5, 2] After Collections.reverse(): [2, 5, 2, -1, -1] ✓

The Code

Edge Cases

1. Strictly decreasing array — Input: [5, 4, 3, 2, 1] Output: [4, 3, 2, 1, -1] Each element's next smaller is simply the next element in the array. Last element is always -1.
2. Strictly increasing array — Input: [1, 2, 3, 4, 5] Output: [-1, -1, -1, -1, -1] No element has a smaller element to its right since the array only grows.
3. Last element is always -1 — nothing exists to its right regardless of its value.
4. Single element — Input: [42] Output: [-1]

Why 36.26% accuracy on GFG? The most common mistake is keeping the NGR pop condition (arr[i] >= st.peek()) and only changing the problem description in your head. The pop condition must flip to arr[i] <= st.peek() for NSR. Forgetting this gives completely wrong answers that look plausible, which makes the bug hard to spot.

Problem 4 — Next Smaller Element to Left / Previous Smaller Element (NSL)

GFG Problem: Search "Previous Smaller Element" on GeeksForGeeks

The Question

For each element in the array, find the first element to its left that is strictly smaller than it. If none exists, return -1.

Input: [4, 8, 5, 2, 25] Output: [-1, 4, 4, -1, 2]

Real World Example

Same warehouse. Now the system looks left instead of right. For the item weighing 8 kg, the first lighter item to its left is 4 kg. For 25 kg, the first lighter to its left is 2 kg. For 4 kg, nothing lighter exists to its left so -1. For 2 kg, nothing lighter to its left so -1. This kind of lookback query appears in time-series analysis, price history tracking, and sensor data processing.

The Intuition

NSL is the mirror of NSR, exactly as NGL was the mirror of NGR. We traverse left to right (no reverse needed). We maintain a stack of candidates from the left. For each element, pop all elements greater than or equal to it — they cannot be the answer since they are not smaller. Whatever remains on top is the first smaller element to the left. Push current and move on.

Step-by-Step Dry Run

Array: [4, 8, 5, 2, 25], traversing left to right.

i=0, element is 4. Stack is empty. Answer is -1. Push 4. Stack: [4]

i=1, element is 8. Top is 4, which is less than 8. Answer is 4. Push 8. Stack: [4, 8]

i=2, element is 5. Top is 8, which is greater than or equal to 5. Pop 8. Top is 4, which is less than 5. Answer is 4. Push 5. Stack: [4, 5]

i=3, element is 2. Top is 5, greater than or equal to 2. Pop 5. Top is 4, greater than or equal to 2. Pop 4. Stack is empty. Answer is -1. Push 2. Stack: [2]

i=4, element is 25. Top is 2, which is less than 25. Answer is 2. Push 25. Stack: [2, 25]

Result: [-1, 4, 4, -1, 2] ✓ No reverse needed.

The Code

Edge Cases

1. First element is always -1 — nothing exists to its left. Stack is empty at i=0 every time.
2. All same elements — Input: [5, 5, 5, 5] Output: [-1, -1, -1, -1] Equal elements do not qualify as smaller. The condition arr[i] <= st.peek() ensures equals are popped and never answer each other.
3. Single element — Input: [9] Output: [-1]

The Master Cheat Sheet

This is the one table to save and refer to whenever you encounter any of these four problems.

Two rules to remember forever:

Rule 1 — Direction. If you are looking to the right, traverse right to left and reverse at the end. If you are looking to the left, traverse left to right and no reverse is needed.

Rule 2 — Pop Condition. If you want a greater element, pop when arr[i] >= st.peek() to clear out smaller useless candidates. If you want a smaller element, pop when arr[i] <= st.peek() to clear out bigger useless candidates.

Mix these two rules and you derive all four variants instantly without memorizing anything separately.

Common Mistakes to Avoid

1. Wrong pop condition — Using > instead of >= in the while loop. This causes duplicate values to wrongly answer each other. Always use >= for greater problems and <= for smaller problems inside the while loop.
2. Forgetting to reverse — For right-to-left traversals (NGR and NSR), you collect answers from right to left. You must call Collections.reverse() before returning. Skipping this is the single most common reason for wrong answers on these problems.
3. Not checking empty stack before peek — Always check !st.empty() before calling st.peek(). An empty stack peek throws EmptyStackException at runtime and will crash your solution.
4. Wrong if-condition after the while loop — After the while loop, the if-condition must use strict comparison. For NGR use st.peek() > arr[i]. For NSR use st.peek() < arr[i]. These must be strict — no equals sign here.
5. Confusing traversal direction with answer direction — You traverse right to left for NGR but the answer array is filled left to right. The reverse at the end handles this. Do not try to index directly into the result array to compensate — just use reverse.

Time and Space Complexity

All four problems run in O(n) time and use O(n) space.

Even though there is a while loop nested inside the for loop, each element is pushed into the stack exactly once and popped from the stack at most once. So across the entire traversal, the total number of push and pop operations combined is at most 2n — which gives O(n) overall. This is the beauty of the monotonic stack.

Why These Four Problems Matter Beyond GFG

These four patterns are not just textbook exercises. They appear as the hidden sub-problem inside some of the hardest stack questions:-

1. Largest Rectangle in Histogram uses NSR and NSL to find the left and right boundaries of each bar.
2. Trapping Rain Water uses NGR and NGL to determine the water level above each position.
3. Stock Span Problem is literally NGL applied directly to stock prices.
4. Sum of Subarray Minimums uses NSR and NSL together to count contributions of each element.

Once you master these four patterns deeply, a whole family of hard problems that previously seemed unapproachable suddenly becomes a matter of recognizing the pattern and applying it.

Also on This Blog

If you are building your stack foundation from scratch, check out the complete deep-dive here → Stack Data Structure in Java: The Complete Guide — covering everything from what a stack is, LIFO principle, all three implementations, every operation with code, and six practice problems.