Previous Greater Element for Each Array Position
Solve this Problemarr, find, for every position, the nearest element to its left that is strictly greater than it — or -1 if no such element exists.
Scanning backward from scratch for every position works but repeats a lot of comparisons unnecessarily. A monotonic stackA stack kept deliberately in sorted order (here, strictly decreasing from bottom to top) by discarding entries that a new arrival makes permanently unreachable as an answer. of strictly decreasing values fixes this in one left-to-right pass: whenever a new element arrives, everything smaller-or-equal sitting on top of the stack can never be anyone's "previous greater" answer again — the new, bigger, closer element would always be found first — so those entries are popped and discarded for good. Whatever survives on top after popping is exactly the answer for the current position.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ arr.length ≤ 15 - ◆
0 ≤ arr[i] ≤ 1000
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Scan Backward for Each Position
BruteFor every position i, scan backward from i-1 toward the start, looking for the first value strictly greater than arr[i]. The first one found (closest to i) is the answer; if the scan reaches the beginning without finding one, the answer is -1. Correct, but each position can trigger a scan through nearly the whole array before it — O(n) per position, O(n²) overall.
O(n²)O(n)1class Solution {
2 public int[] previousGreaterElement(int[] arr) {
3 int n = arr.length;
4 int[] result = new int[n];
5 for (int i = 0; i < n; i++) {
6 result[i] = -1;
7 for (int j = i - 1; j >= 0; j--) {
8 if (arr[j] > arr[i]) {
9 result[i] = arr[j];
10 break;
11 }
12 }
13 }
14 return result;
15 }
16}Optimal — Monotonic Decreasing Stack
OptimalKeep a stack that only ever holds values in strictly decreasing order from bottom to top. For each new element, first pop off anything on top that's less than or equal to it — those values can never be the answer for this or any later element, since the current element is greater and closer. Whatever's left on top after popping (if anything) is exactly the nearest greater element to the left. Push the current value and move on. Every value is pushed once and popped at most once, so the total work across the whole array is O(n).
O(n)O(n)1class Solution {
2 public int[] previousGreaterElement(int[] arr) {
3 int n = arr.length;
4 int[] result = new int[n];
5 Deque<Integer> stack = new ArrayDeque<>();
6 for (int i = 0; i < n; i++) {
7 while (!stack.isEmpty() && stack.peek() <= arr[i]) {
8 stack.pop();
9 }
10 result[i] = stack.isEmpty() ? -1 : stack.peek();
11 stack.push(arr[i]);
12 }
13 return result;
14 }
15}