Next Greater Value From a Reference Sequence
Solve this Problemqueries, a list of values to look up, and reference, a sequence in which every value in queries is guaranteed to appear exactly once. For every value in queries, find the first value in reference that comes strictly after it and is strictly greater — or -1 if none exists.
Looking each query up individually — locate it, then scan forward — repeats the same kind of scan over and over. It's faster to flip the order of work: make a single left-to-right pass over reference with a monotonic decreasing stack, recording every element's "next greater" answer into a map the moment it's discovered (exactly the moment a bigger value causes it to be popped). Once that map is built, every query in the list becomes an O(1) lookup, turning what could be O(n·m) repeated scanning into O(n + m) total work.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ queries.length ≤ 10 - ◆
1 ≤ reference.length ≤ 15 - ◆
0 ≤ queries[i], reference[i] ≤ 1000 - ◆
All values inside reference are distinct - ◆
Every value in queries is guaranteed to appear somewhere in reference
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Locate Then Scan Forward for Each Query
BruteFor every value in queries, first find where it sits inside reference by scanning for it, then scan forward from just past that position looking for the first strictly greater value. If the forward scan reaches the end without finding one, the answer is -1. This works but repeats a full linear search (locate + scan) independently for every query, giving O(n) work per query and O(n·m) overall.
O(n·m)O(m)1class Solution {
2 public int[] nextGreaterFromReference(int[] queries, int[] reference) {
3 int m = queries.length, n = reference.length;
4 int[] result = new int[m];
5 for (int i = 0; i < m; i++) {
6 int idx = -1;
7 for (int k = 0; k < n; k++) {
8 if (reference[k] == queries[i]) { idx = k; break; }
9 }
10 result[i] = -1;
11 for (int j = idx + 1; j < n; j++) {
12 if (reference[j] > queries[i]) {
13 result[i] = reference[j];
14 break;
15 }
16 }
17 }
18 return result;
19 }
20}Optimal — Precompute With a Monotonic Stack, Then Look Up
OptimalSeparate the problem into two clean phases. First, walk reference once, left to right, with a monotonic decreasing stack: whenever a new value is bigger than what's on top of the stack, everything smaller gets popped and its answer is recorded as this new value in a map — that's the same "previous greater" logic run in reverse, computing "next greater" for every value in reference in a single O(n) pass. Second, answer every query in O(1) with a simple map lookup. Total work is O(n + m) instead of O(n·m).
O(n + m)O(n)1class Solution {
2 public int[] nextGreaterFromReference(int[] queries, int[] reference) {
3 Map<Integer, Integer> nextGreater = new HashMap<>();
4 Deque<Integer> stack = new ArrayDeque<>();
5 for (int x : reference) {
6 while (!stack.isEmpty() && stack.peek() < x) {
7 nextGreater.put(stack.pop(), x);
8 }
9 stack.push(x);
10 }
11 int[] result = new int[queries.length];
12 for (int i = 0; i < queries.length; i++) {
13 result[i] = nextGreater.getOrDefault(queries[i], -1);
14 }
15 return result;
16 }
17}