Log inSign up
easyLeetCodeNot Started

Next Greater Element I

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Stack
Solve on LeetCode
Lesson

Problem Statement

The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.

You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.

For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.

Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

Example 1 · Standard Subset Query:

Input: nums1 = [4, 1, 2], nums2 = [1, 3, 4, 2]
Output: [-1, 3, -1]
Explanation: For 4: in nums2 [1, 3, 4, 2], no element to the right is greater -> -1. For 1: next greater to the right is 3. For 2: no element to the right -> -1.

Example 2 · All Greater Elements Exist:

Input: nums1 = [2, 4], nums2 = [1, 2, 3, 4]
Output: [3, -1]
Explanation: For 2: next greater is 3. For 4: no elements to the right -> -1.

Constraints:

  • 1 <= nums1.length <= nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 104
  • All integers in nums1 and nums2 are unique.
  • All elements of nums1 appear in nums2.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the classic Next Greater Element monotonic stack template.
  • Combine monotonic stacks with hash maps to achieve O(1) query lookups.
  • Understand the amortized O(N) traversal property.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Algorithmic Decision Tree:

  • Use Monotonic Stack on nums2 to find Next Greater Element for all numbers.
  • Store mappings { element: nextGreaterElement } in a Hash Table.
  • Query each number from nums1 directly in the Hash Table.

Connected Patterns:

Next Greater Element IIDaily TemperaturesNext Smaller Element

1. Linear Search for Every Query

Intuition

For every query element x in nums1, locate x in nums2 and then iterate rightwards until a strictly greater element is found.

Algorithm

  1. Step 1: Initialize result array ans of size nums1.length.
  2. Step 2: For each element nums1[i], find its index idx in nums2.
  3. Step 3: Scan nums2 from idx + 1 to nums2.length - 1.
  4. Step 4: If nums2[j] > nums1[i], record ans[i] = nums2[j] and break. If none found, set ans[i] = -1.
  5. Step 5: Return ans.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 std::vector<int> nextGreaterElement(std::vector<int>& nums1, std::vector<int>& nums2) {
7 std::vector<int> ans(nums1.size(), -1);
8 for (size_t i = 0; i < nums1.size(); i++) {
9 int target = nums1[i];
10 int idx = -1;
11 for (size_t j = 0; j < nums2.size(); j++) {
12 if (nums2[j] == target) {
13 idx = j;
14 break;
15 }
16 }
17 for (size_t j = idx + 1; j < nums2.size(); j++) {
18 if (nums2[j] > target) {
19 ans[i] = nums2[j];
20 break;
21 }
22 }
23 }
24 return ans;
25 }
26};
27
28int main() {
29 Solution solver;
30 std::vector<int> nums1 = {4, 1, 2};
31 std::vector<int> nums2 = {1, 3, 4, 2};
32 std::vector<int> ans = solver.nextGreaterElement(nums1, nums2);
33 std::cout << "Output: [";
34 for (size_t i = 0; i < ans.size(); i++) {
35 std::cout << ans[i] << (i + 1 < ans.size() ? ", " : "");
36 }
37 std::cout << "]" << std::endl;
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(M * N) — For each element in nums1 (size M), find its position in nums2 (size N) and scan to the right to find the next greater element.
  • Space complexity: O(1) — O(1) auxiliary space beyond the output array.

Why Brute Force Doesn't Scale:

When M and N are large (e.g. 105), O(M * N) = 1010 operations.

Monotonic Stack precomputes answers in 1 pass O(N) and answers all M queries in O(M).

2. Hash Map Position Indexing

Intuition

Instead of linearly searching for the position of nums1[i] in nums2, use a hash map to look up its index in O(1), then scan right.

Algorithm

  1. Step 1: Build a hash map pos mapping nums2[i] -> i.
  2. Step 2: For each x in nums1, retrieve idx = pos[x] in O(1).
  3. Step 3: Scan nums2 from idx + 1 to find the next greater element.
  4. Step 4: Return result array.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4
5class Solution {
6public:
7 std::vector<int> nextGreaterElement(std::vector<int>& nums1, std::vector<int>& nums2) {
8 std::unordered_map<int, int> pos;
9 for (int i = 0; i < (int)nums2.size(); i++) {
10 pos[nums2[i]] = i;
11 }
12 std::vector<int> ans(nums1.size(), -1);
13 for (size_t i = 0; i < nums1.size(); i++) {
14 int startIdx = pos[nums1[i]];
15 for (size_t j = startIdx + 1; j < nums2.size(); j++) {
16 if (nums2[j] > nums1[i]) {
17 ans[i] = nums2[j];
18 break;
19 }
20 }
21 }
22 return ans;
23 }
24};
25
26int main() {
27 Solution solver;
28 std::vector<int> nums1 = {4, 1, 2};
29 std::vector<int> nums2 = {1, 3, 4, 2};
30 std::vector<int> ans = solver.nextGreaterElement(nums1, nums2);
31 std::cout << "Output: [";
32 for (size_t i = 0; i < ans.size(); i++) {
33 std::cout << ans[i] << (i + 1 < ans.size() ? ", " : "");
34 }
35 std::cout << "]" << std::endl;
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(N + M * N) — Precomputing indices of nums2 elements in a hash map reduces lookup of index to O(1), though scanning rightwards remains O(N) per query.
  • Space complexity: O(N) — O(N) hash map to store indices.

3. Optimal Monotonic Stack + Hash Map

Intuition

Use a monotonic decreasing stack to precompute the next greater element for every number in nums2. Store results in a map {num: nextGreater}. Then look up each element of nums1 in O(1).

Algorithm

  1. Step 1: Initialize an empty stack st and a hash map nextGreaterMap.
  2. Step 2: Iterate through each num in nums2.
  3. Step 3: While stack is not empty and num > st.top(), pop top = st.top() and record nextGreaterMap[top] = num.
  4. Step 4: Push num onto st.
  5. Step 5: For each x in nums1, answer nextGreaterMap.get(x, -1).
  6. Step 6: Return the mapped array.

Monotonic Stack Next Greater Precomputation

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Stack: [1]
Visual state
Values and pointers at this exact step
stack
TOP
1
Push adds to the top · Pop removes from the top
Why this step matters

Stack: [1]

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <stack>
4#include <unordered_map>
5
6class Solution {
7public:
8 std::vector<int> nextGreaterElement(std::vector<int>& nums1, std::vector<int>& nums2) {
9 std::unordered_map<int, int> nextGreater;
10 std::stack<int> st;
11 for (int num : nums2) {
12 while (!st.empty() && num > st.top()) {
13 nextGreater[st.top()] = num;
14 st.pop();
15 }
16 st.push(num);
17 }
18 std::vector<int> ans;
19 ans.reserve(nums1.size());
20 for (int x : nums1) {
21 ans.push_back(nextGreater.count(x) ? nextGreater[x] : -1);
22 }
23 return ans;
24 }
25};
26
27int main() {
28 Solution solver;
29 std::vector<int> nums1 = {4, 1, 2};
30 std::vector<int> nums2 = {1, 3, 4, 2};
31 std::vector<int> ans = solver.nextGreaterElement(nums1, nums2);
32 std::cout << "Output: [";
33 for (size_t i = 0; i < ans.size(); i++) {
34 std::cout << ans[i] << (i + 1 < ans.size() ? ", " : "");
35 }
36 std::cout << "]" << std::endl;
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(N + M) — Single O(N) pass over nums2 with a monotonic stack populating a hash map, followed by O(M) queries over nums1.
  • Space complexity: O(N) — O(N) space for the stack and hash map holding next greater mappings.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Linear Search for Every QueryO(M * N)O(1)Scan nums2 from target index to find next greater element for each query.Quadratic worst-case scaling.
2.Hash Map Position IndexingO(N + M * N)O(N)O(1) starting index lookup via Hash Map followed by linear right-scan.Rightwards linear scans.
3.Optimal Monotonic Stack + Hash MapOptimalO(N + M)O(N)Single pass over nums2 precomputes answers for all numbers into a map.None (Optimal).

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Searching inside nums1 instead of nums2.

Pitfall 2:

Using < instead of > when checking if current number resolves the stack top.

Pitfall 3:

Not handling default -1 for elements that never got popped.

Crucial Edge Cases to Validate:

  • Strictly decreasing `nums2` (e.g. `[5, 4, 3, 2, 1]`) — All queries return -1.
  • Strictly increasing `nums2` (e.g. `[1, 2, 3, 4, 5]`) — Every element's next greater is its immediate right neighbor.
  • Single element arrays `nums1 = [1], nums2 = [1]` — Output [-1].
  • `nums1` is equal to `nums2` — Computes next greater for all elements.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clearly highlight that nums1 is a subset of nums2, which motivates precomputing answers for nums2 in a Hash Table.
  2. Show the connection between monotonic decreasing stacks and finding the Next Greater Element.
  3. State the space/time trade-off clearly: O(N) space for O(N + M) time.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why can we store values directly in the hash map instead of array indices?

2.What happens to elements left inside the stack when traversal of nums2 finishes?

Back to DSA Sheet