Nearest greater/smaller elements and range extremums in linear time
Maintain a stack with strictly increasing or decreasing elements to find the Nearest Greater or Smaller Element for all elements in O(N) total time.
Core Invariant: Every element is pushed once and popped at most once. Pushing an element pops all elements that violate monotonicity, meaning the incoming element IS their Next Greater/Smaller answer!
Need arbitrary lookups across non-monotonic boundaries or dynamic insertions with k-th queries (use Heap or BST).
def next_greater_elements(nums: list[int]) -> list[int]:
n = len(nums)
res = [-1] * n
stack = [] # Stores indices of unresolved elements
for i in range(n):
# Pop all elements smaller than current element nums[i]
while stack and nums[i] > nums[stack[-1]]:
popped_idx = stack.pop()
res[popped_idx] = nums[i] # nums[i] is the next greater element!
stack.append(i)
return res# | Problem | Difficulty | Top Companies↓ | Frequency | Acceptance | |
|---|---|---|---|---|---|---|
| #42 | Trapping Rain Water ArrayTwo PointersDynamic ProgrammingStackMonotonic Stack | Hard | 100% | 67.7% | ||
| #239 | Sliding Window Maximum ArrayQueueSliding WindowHeap (Priority Queue)Monotonic QueueRange Minimum/Maximum Query | Hard | 100% | 49.0% | ||
| #735 | Asteroid Collision ArrayStackSimulation | Medium | 100% | 48.4% | ||
| #739 | Daily Temperatures ArrayStackMonotonic Stack | Medium | 100% | 68.9% | ||
| #84 | Largest Rectangle in Histogram ArrayStackMonotonic StackRange Minimum/Maximum Query | Hard | 92% | 50.3% | ||
| #402 | Remove K Digits StringStackGreedyMonotonic Stack | Medium | 100% | 37.2% | ||
| #503 | Next Greater Element II ArrayStackMonotonic Stack | Medium | 87% | 68.7% | ||
| #1438 | Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit ArrayQueueSliding WindowHeap (Priority Queue)Ordered SetMonotonic Queue | Medium | 100% | 0.6% | ||
| #1944 | Number of Visible People in a Queue ArrayStackMonotonic Stack | Hard | 81% | 73.3% | ||
| #85 | Maximal Rectangle ArrayDynamic ProgrammingStackMatrixMonotonic Stack | Hard | 83% | 0.6% | ||
| #496 | Next Greater Element I ArrayHash TableStackMonotonic Stack | Easy | 82% | 76.5% | ||
| #907 | Sum of Subarray Minimums ArrayDynamic ProgrammingStackMonotonic Stack | Medium | 88% | 0.4% | ||
| #316 | Remove Duplicate Letters StringStackGreedyMonotonic Stack | Medium | 100% | 53.5% | ||
| #853 | Car Fleet ArrayStackSortingMonotonic Stack | Medium | 100% | 55.4% | ||
| #918 | Maximum Sum Circular Subarray ArrayDivide and ConquerDynamic ProgrammingQueueMonotonic Queue | Medium | 90% | 50.7% | ||
| #556 | Next Greater Element III MathTwo PointersString | Medium | 66% | 0.4% | ||
| #2444 | Count Subarrays With Fixed Bounds ArrayQueueSliding WindowMonotonic Queue | Hard | 88% | 69.2% | ||
| #1081 | Smallest Subsequence of Distinct Characters StringStackGreedyMonotonic Stack | Medium | 100% | 0.7% | ||
| #862 | Shortest Subarray with Sum at Least K ArrayBinary SearchQueueSliding WindowHeap (Priority Queue)Prefix SumMonotonic Queue | Hard | 100% | 32.9% | ||
| #581 | Shortest Unsorted Continuous Subarray ArrayTwo PointersStackGreedySortingMonotonic Stack | Medium | 100% | 38.4% | ||
| #1574 | Shortest Subarray to be Removed to Make Array Sorted ArrayTwo PointersBinary SearchStackMonotonic Stack | Medium | 97% | 51.4% | ||
| #2104 | Sum of Subarray Ranges ArrayStackMonotonic Stack | Medium | 88% | 61.5% | ||
| #962 | Maximum Width Ramp ArrayTwo PointersStackMonotonic Stack | Medium | 88% | 55.9% | ||
| #1526 | Minimum Number of Increments on Subarrays to Form a Target Array ArrayDynamic ProgrammingStackGreedyMonotonic Stack | Hard | 68% | 0.8% | ||
| #321 | Create Maximum Number ArrayTwo PointersStackGreedyMonotonic Stack | Hard | 64% | 0.4% | ||
| #456 | 132 Pattern ArrayBinary SearchStackMonotonic StackOrdered Set | Medium | 54% | 34.9% | ||
| #901 | Online Stock Span StackDesignMonotonic StackData Stream | Medium | 50% | 69.4% | ||
| #1475 | Final Prices With a Special Discount in a Shop ArrayStackMonotonic Stack | Easy | 100% | 84.2% | ||
| #1696 | Jump Game VI ArrayDynamic ProgrammingQueueHeap (Priority Queue)Monotonic Queue | Medium | 100% | 46.5% | ||
| #769 | Max Chunks To Make Sorted ArrayStackGreedySortingMonotonic Stack | Medium | 77% | 64.2% | ||
| #1008 | Construct Binary Search Tree from Preorder Traversal ArrayStackTreeBinary Search TreeMonotonic StackBinary Tree | Medium | 43% | 84.4% | ||
| #255 | Verify Preorder Sequence in Binary Search Tree ArrayStackTreeBinary Search TreeRecursionMonotonic StackBinary Tree | Medium | 100% | 51.8% | ||
| #1762 | Buildings With an Ocean View ArrayStackMonotonic Stack | Medium | 88% | 80.9% | ||
| #2071 | Maximum Number of Tasks You Can Assign ArrayTwo PointersBinary SearchGreedyQueueSortingMonotonic Queue | Hard | 88% | 50.0% | ||
| #2940 | Find Building Where Alice and Bob Can Meet ArrayBinary SearchStackBinary Indexed TreeSegment TreeHeap (Priority Queue)Monotonic Stack | Hard | 75% | 52.4% | ||
| #1019 | Next Greater Node In Linked List ArrayLinked ListStackMonotonic Stack | Medium | 58% | 64.5% | ||
| #2762 | Continuous Subarrays ArrayQueueSliding WindowHeap (Priority Queue)Ordered SetMonotonic Queue | Medium | 38% | 58.0% | ||
| #768 | Max Chunks To Make Sorted II ArrayStackGreedySortingMonotonic Stack | Hard | 28% | 55.0% | ||
| #1130 | Minimum Cost Tree From Leaf Values ArrayDynamic ProgrammingStackGreedyMonotonic StackCartesian Tree | Medium | 90% | 67.9% | ||
| #3878 | Count Good Subarrays ArrayStackBit ManipulationMonotonic Stack | Hard | 89% | 0.3% | ||
| #2866 | Beautiful Towers II ArrayStackMonotonic Stack | Medium | 65% | 0.4% | ||
| #1856 | Maximum Subarray Min-Product ArrayStackMonotonic StackPrefix SumCartesian Tree | Medium | 52% | 0.4% | ||
| #654 | Maximum Binary Tree ArrayDivide and ConquerStackTreeMonotonic StackBinary TreeCartesian Tree | Medium | 28% | 86.4% | ||
| #1504 | Count Submatrices With All Ones ArrayDynamic ProgrammingStackMatrixMonotonic Stack | Medium | 27% | 71.0% | ||
| #2487 | Remove Nodes From Linked List Linked ListStackRecursionMonotonic Stack | Medium | 25% | 75.0% | ||
| #3542 | Minimum Operations to Convert All Elements to Zero ArrayHash TableStackGreedyMonotonic Stack | Medium | 18% | 53.1% | ||
| #3578 | Count Partitions With Max-Min Difference at Most K ArrayDynamic ProgrammingQueueSliding WindowPrefix SumMonotonic Queue | Medium | 13% | 58.5% | ||
| #2617 | Minimum Number of Visited Cells in a Grid ArrayDynamic ProgrammingStackBreadth-First SearchUnion-FindHeap (Priority Queue)MatrixMonotonic Stack | Hard | 100% | 24.0% | ||
| #1124 | Longest Well-Performing Interval ArrayHash TableStackMonotonic StackPrefix Sum | Medium | 75% | 37.9% | ||
| #975 | Odd Even Jump ArrayDynamic ProgrammingStackSortingMonotonic StackOrdered Set | Hard | 65% | 41.3% |
Browse company-specific interview problem lists and recency breakdowns:
Master core algorithmic patterns tested in FAANG & Big Tech coding interviews.
Nearest greater/smaller elements and range extremums in linear time It is categorized under Data Structures and features 85 curated interview problems across Easy (2), Medium (50), and Hard (33) difficulties.
Companies frequently asking Monotonic Stack & Queue questions include Google, Amazon, Microsoft, Meta, Bloomberg, TikTok.
Start by studying the algorithmic strategy and template code, then practice Easy and Medium problems before attempting Hard problems under timed conditions.