What pattern does Next Greater Element I use?

The Pattern: Stack (Monotonic Stack for Next Greater Element) The Heuristic: Maintain a stack of elements in decreasing order; when a new element is greater than the stack's top, it is the next greater element for all smaller elements popped from the stack, enabling a single-pass O(n) solution.

Next Greater Element I - LeetCode Solution

Q: What is the time complexity of Next Greater Element I?

O(n + m). Each element in nums2 is pushed and popped at most once from the stack, resulting in O(n) time. Then, building the result for nums1 takes O(m) time, where n = len(nums2) and m = len(nums1).

Problem

Given two integer arrays nums1 and nums2 where nums1 is a subset of nums2, return an array of the next greater elements for nums1's elements in nums2. The next greater element of a number x in nums2 is the first greater number to the right of x in nums2; if it does not exist, return -1 for that number.

1 ≤ nums1.length ≤ nums2.length ≤ 1000
0 ≤ nums1[i], nums2[i] ≤ 10⁴
All elements in nums1 and nums2 are unique
nums1 is a subset of nums2

Example

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]

Output: [-1,3,-1]

The algorithm processes nums2 to find the next greater element for each number. Starting with nums2: [1,3,4,2], it uses a stack to track elements waiting for their next greater number. When it sees 3 after 1, it records that 3 is the next greater for 1. Then it sees 4 after 3, which is the next greater for 3. The number 2 has no greater number to its right, so it maps to -1. Using this mapping, the algorithm looks up each element in nums1: 4 maps to -1 (no greater element), 1 maps to 3, and 2 maps to -1.

Approach

Straightforward Solution

A brute-force approach checks, for each element in nums1, all elements to the right in nums2 to find the next greater element. This results in O(n*m) time complexity, which is inefficient for larger inputs.

Core Observation

The next greater element for any number in nums2 depends on the elements to its right. A stack can efficiently track elements for which the next greater element is not yet found by maintaining a decreasing sequence.

Path to Optimal

The key recognition signals are 'next greater element', 'to the right', and 'unique elements'. These indicate a Monotonic Stack pattern because the problem requires efficiently finding the next greater element for multiple numbers in a sequence. Using a stack to maintain a decreasing sequence allows processing nums2 in a single pass, mapping each element to its next greater element in O(n) time.

Optimal Approach

Iterate through nums2 once, using a stack to keep track of elements waiting for their next greater element. When a new number is greater than the top of the stack, pop from the stack and record the new number as the next greater element for the popped number. After processing nums2, use the mapping to build the result for nums1, returning -1 if no next greater element exists.

Time

O(n + m)

Each element in nums2 is pushed and popped at most once from the stack, resulting in O(n) time. Then, building the result for nums1 takes O(m) time, where n = len(nums2) and m = len(nums1).

Space

O(n)

The stack and the next_greater dictionary each store up to n elements from nums2, resulting in O(n) auxiliary space.

Solution

1class Solution:
  def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
      stack = []
      next_greater = {}
5
      for num in nums2:
          while stack and stack[-1] < num:
              next_greater[stack.pop()] = num
          stack.append(num)
10
      res = []
      for num in nums1:
          if num in next_greater:
              res.append(next_greater[num])
          else:
              res.append(-1)
17
      return res

1import java.util.*;
2
3class Solution {
4    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
5        Deque<Integer> stack = new ArrayDeque<>();
6        Map<Integer, Integer> nextGreater = new HashMap<>();
7
8        for (int num : nums2) {
9            while (!stack.isEmpty() && stack.peekLast() < num) {
10                nextGreater.put(stack.pollLast(), num);
11            }
12            stack.addLast(num);
13        }
14
15        int[] res = new int[nums1.length];
16        for (int i = 0; i < nums1.length; i++) {
17            res[i] = nextGreater.getOrDefault(nums1[i], -1);
18        }
19
20        return res;
21    }
22}

1#include <vector>
2#include <unordered_map>
3#include <stack>
4
5using namespace std;
6
7class Solution {
8public:
9    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
10        stack<int> stk;
11        unordered_map<int, int> next_greater;
12
13        for (int num : nums2) {
14            while (!stk.empty() && stk.top() < num) {
15                next_greater[stk.top()] = num;
16                stk.pop();
17            }
18            stk.push(num);
19        }
20
21        vector<int> res;
22        res.reserve(nums1.size());
23        for (int num : nums1) {
24            if (next_greater.find(num) != next_greater.end()) {
25                res.push_back(next_greater[num]);
26            } else {
27                res.push_back(-1);
28            }
29        }
30
31        return res;
32    }
33};

1var nextGreaterElement = function(nums1, nums2) {
  const stack = [];
  const nextGreater = new Map();
4
  for (const num of nums2) {
      while (stack.length > 0 && stack[stack.length - 1] < num) {
          nextGreater.set(stack.pop(), num);
      }
      stack.push(num);
  }
11
  const res = [];
  for (const num of nums1) {
      res.push(nextGreater.has(num) ? nextGreater.get(num) : -1);
  }
16
  return res;
18};

Step-by-Step Solution

1

Build Next Greater Element Mapping by Processing nums2

3stack = []
4next_greater = {}
6for num in nums2:
7    while stack and stack[-1] < num:
8        next_greater[stack.pop()] = num
9    stack.append(num)

Objective

To create a mapping from each element in nums2 to its next greater element using a monotonic stack.

Key Insight

By iterating through nums2 and maintaining a stack of elements in decreasing order, the algorithm identifies the next greater element for each number as soon as a larger number appears. This approach avoids nested loops and achieves O(n) time by ensuring each element is pushed and popped at most once.

Interview Quick-Check

Core Logic

The stack maintains a decreasing sequence of numbers; when a new number is greater than the stack's top, it is the next greater element for all smaller elements popped from the stack.

State & Boundaries

The while loop continues popping until the stack is empty or the top is greater than or equal to the current number, ensuring the stack remains decreasing.

Common Pitfalls & Bugs

Failing to pop all smaller elements before pushing the current number leads to incorrect mappings or missed next greater elements.

Complexity

Each element is pushed and popped at most once, guaranteeing O(n) time complexity for this step.

2

Construct Result Array for nums1 Using the Mapping

11res = []
12for num in nums1:
13    if num in next_greater:
14        res.append(next_greater[num])
15    else:
16        res.append(-1)

Objective

To build the output array by looking up the next greater element for each number in nums1 using the precomputed mapping.

Key Insight

After mapping all next greater elements from nums2, the algorithm efficiently constructs the result for nums1 by direct dictionary lookups, returning -1 when no next greater element exists. This avoids repeated searches and leverages the precomputation for O(m) time complexity.

Interview Quick-Check

Core Logic

Lookup in the next_greater dictionary provides O(1) access to the next greater element for each number in nums1.

State & Boundaries

If a number from nums1 is not in the mapping, it means no next greater element exists, so append -1.

Common Pitfalls & Bugs

Forgetting to handle the case where a number has no next greater element leads to incorrect results.

Complexity

This step runs in O(m) time, where m is the length of nums1.

3

Return the Final Result Array

18	`return res`

Objective

To return the constructed list of next greater elements corresponding to nums1.

Key Insight

Returning the precomputed result completes the algorithm, providing the answer in O(1) time after all preprocessing and lookups.

Interview Quick-Check

Core Logic

Return the result list after all next greater elements have been determined.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 7 Critical

while stack and stack[-1] < num:

While the stack is not empty and the current number is greater than the top of the stack, pop from the stack.

This loop identifies all elements smaller than the current number that have found their next greater element, ensuring the stack remains decreasing.

Line 8 Critical

next_greater[stack.pop()] = num

Map the popped element to the current number as its next greater element.

Assigning the current number as the next greater element for the popped smaller element is the key step that records the solution for that element.

Line 3 Core

stack = []

Initialize an empty stack to track elements waiting for their next greater element.

The stack is the core data structure enabling the monotonic stack approach, maintaining a decreasing sequence to efficiently find next greater elements.

Line 4 Core

next_greater = {}

Initialize a dictionary to map each element to its next greater element.

This dictionary stores the final mapping from each number in nums2 to its next greater element, enabling O(1) lookups later.

Line 9 Core

stack.append(num)

Push the current number onto the stack to await its next greater element.

Adding the current number maintains the decreasing stack invariant and prepares for future comparisons.

Line 13 Core

if num in next_greater:

Check if the current number has a next greater element in the mapping.

This conditional determines whether to append the mapped next greater element or -1 if none exists.

Line 16 Core

res.append(-1)

Append -1 to the result list if no next greater element exists.

Appending -1 correctly represents the absence of a next greater element, as required by the problem.

Line 6 Standard

for num in nums2:

Iterate through each number in nums2 to build the mapping.

Processing nums2 in order is essential because the next greater element depends on elements to the right.

Line 12 Standard

for num in nums1:

Iterate through each number in nums1 to build the result.

Each element in nums1 requires a lookup in the next_greater mapping to find its next greater element.

Line 14 Standard

res.append(next_greater[num])

Append the next greater element to the result list.

Appending the mapped value preserves the correct order and completes the lookup for this element.

Line 11 Standard

res = []

Initialize an empty list to store the results for nums1.

This list accumulates the next greater elements corresponding to nums1's elements, preserving order.

Line 18 Standard

return res

Return the list of next greater elements for nums1.

Returning the result completes the function, providing the final answer to the caller.

Line 15 Basic

else:

Handle the case where the current number has no recorded next greater element.

This else branch handles the fallback case when the current value from nums1 does not appear in the next_greater mapping, which means no greater element was found to its right in nums2.

Test Your Understanding

Why does using a stack to maintain a decreasing sequence allow us to find the next greater element for all elements in a single pass?

Because the stack holds elements waiting for their next greater element, and when a new number is greater than the stack's top, it must be the next greater element for all smaller elements popped, ensuring each element is processed exactly once.

Don't just read it. Drill it.

Reconstruct Next Greater Element I from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Next Greater Element I drill

or drill a free problem

1	`class Solution:`
2	`def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:`
3	`stack = []`
4	`next_greater = {}`
5
6	`for num in nums2:`
7	`while stack and stack[-1] < num:`
8	`next_greater[stack.pop()] = num`
9	`stack.append(num)`
10
11	`res = []`
12	`for num in nums1:`
13	`if num in next_greater:`
14	`res.append(next_greater[num])`
15	`else:`
16	`res.append(-1)`
17
18	`return res`

1	`import java.util.*;`
2
3	`class Solution {`
4	`public int[] nextGreaterElement(int[] nums1, int[] nums2) {`
5	`Deque<Integer> stack = new ArrayDeque<>();`
6	`Map<Integer, Integer> nextGreater = new HashMap<>();`
7
8	`for (int num : nums2) {`
9	`while (!stack.isEmpty() && stack.peekLast() < num) {`
10	`nextGreater.put(stack.pollLast(), num);`
11	`}`
12	`stack.addLast(num);`
13	`}`
14
15	`int[] res = new int[nums1.length];`
16	`for (int i = 0; i < nums1.length; i++) {`
17	`res[i] = nextGreater.getOrDefault(nums1[i], -1);`
18	`}`
19
20	`return res;`
21	`}`
22	`}`

1	`#include <vector>`
2	`#include <unordered_map>`
3	`#include <stack>`
4
5	`using namespace std;`
6
7	`class Solution {`
8	`public:`
9	`vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {`
10	`stack<int> stk;`
11	`unordered_map<int, int> next_greater;`
12
13	`for (int num : nums2) {`
14	`while (!stk.empty() && stk.top() < num) {`
15	`next_greater[stk.top()] = num;`
16	`stk.pop();`
17	`}`
18	`stk.push(num);`
19	`}`
20
21	`vector<int> res;`
22	`res.reserve(nums1.size());`
23	`for (int num : nums1) {`
24	`if (next_greater.find(num) != next_greater.end()) {`
25	`res.push_back(next_greater[num]);`
26	`} else {`
27	`res.push_back(-1);`
28	`}`
29	`}`
30
31	`return res;`
32	`}`
33	`};`

1	`var nextGreaterElement = function(nums1, nums2) {`
2	`const stack = [];`
3	`const nextGreater = new Map();`
4
5	`for (const num of nums2) {`
6	`while (stack.length > 0 && stack[stack.length - 1] < num) {`
7	`nextGreater.set(stack.pop(), num);`
8	`}`
9	`stack.push(num);`
10	`}`
11
12	`const res = [];`
13	`for (const num of nums1) {`
14	`res.push(nextGreater.has(num) ? nextGreater.get(num) : -1);`
15	`}`
16
17	`return res;`
18	`};`

3	`stack = []`
4	`next_greater = {}`
6	`for num in nums2:`
7	`while stack and stack[-1] < num:`
8	`next_greater[stack.pop()] = num`
9	`stack.append(num)`

Problem

Example

Approach

Solution

Step-by-Step Solution

Build Next Greater Element Mapping by Processing nums2

Construct Result Array for nums1 Using the Mapping

Return the Final Result Array

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.