Next Greater Element
For each element in an array, find the next greater element to its right. The naive O(n²) solution checks every pair. The optimal solution uses a monotonic decreasing stack to achieve O(n) time. This is an essential pattern appearing in stock span, temperature problems, and many interval-based challenges. The technique extends to circular arrays and next smaller elements.
Visualization
Interactive visualization for Next Greater Element
Monotonic Stack (Next Greater Element)
Array:
• Time: O(n) - each element pushed/popped once
• Monotonic stack maintains increasing order
• Used in stock span, histograms, etc.
Interactive visualization with step-by-step execution
Implementation
1function nextGreaterElement(nums: number[]): number[] {
2 const n = nums.length;
3 const result = new Array(n).fill(-1);
4 const stack: number[] = [];
5
6 for (let i = n - 1; i >= 0; i--) {
7 while (stack.length > 0 && stack[stack.length - 1] <= nums[i]) {
8 stack.pop();
9 }
10
11 if (stack.length > 0) {
12 result[i] = stack[stack.length - 1];
13 }
14
15 stack.push(nums[i]);
16 }
17
18 return result;
19}
20
21// For circular array
22function nextGreaterElementCircular(nums: number[]): number[] {
23 const n = nums.length;
24 const result = new Array(n).fill(-1);
25 const stack: number[] = [];
26
27 for (let i = 2 * n - 1; i >= 0; i--) {
28 const idx = i % n;
29
30 while (stack.length > 0 && stack[stack.length - 1] <= nums[idx]) {
31 stack.pop();
32 }
33
34 if (i < n && stack.length > 0) {
35 result[idx] = stack[stack.length - 1];
36 }
37
38 stack.push(nums[idx]);
39 }
40
41 return result;
42}Deep Dive
Theoretical Foundation
Next Greater Element uses a monotonic stack (elements in decreasing order). Traverse right-to-left: when we encounter an element, pop all smaller elements from stack (they can never be 'next greater' for future elements). The remaining top element (if any) is the next greater. Push current element to maintain monotonicity. Key insight: each element is pushed/popped exactly once, giving O(n) time. The stack stores potential 'next greater' candidates in decreasing order. For circular arrays, simulate by traversing array twice (using modulo).
Complexity
Time
O(n)
O(n)
O(n)
Space
O(n)
Applications
Industry Use
Stock span problem (days until stock price higher)
Daily temperatures (days until warmer)
Histogram largest rectangle
Building skyline view
Maximum of subarrays
Expression evaluation
Use Cases
Related Algorithms
Binary Search Tree (BST)
A hierarchical data structure where each node has at most two children, maintaining the property that all values in the left subtree are less than the node's value, and all values in the right subtree are greater. This ordering property enables efficient O(log n) operations on average for search, insert, and delete. BSTs form the foundation for many advanced tree structures and are fundamental in computer science.
Stack
LIFO (Last-In-First-Out) data structure with O(1) push/pop operations. Stack is a fundamental linear data structure where elements are added and removed from the same end (top). It's essential for function calls, expression evaluation, backtracking algorithms, and undo operations in applications.
Queue
FIFO (First-In-First-Out) data structure with O(1) enqueue/dequeue operations. Queue is a fundamental linear data structure where elements are added at one end (rear) and removed from the other end (front). Essential for breadth-first search, task scheduling, and buffering systems.
Hash Table (Hash Map)
A data structure that implements an associative array abstract data type, mapping keys to values using a hash function. Hash tables provide O(1) average-case time complexity for insertions, deletions, and lookups, making them one of the most efficient data structures for key-value storage. The hash function computes an index into an array of buckets from which the desired value can be found.