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 — Monotonic Stack

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

Preview

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…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

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…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

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

Python

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

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

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

3

Return the Final Result Array

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

2 more steps with full analysis available on Pro.

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.

Full line-by-line criticality + rationale for all 13 lines available on Pro.

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?

See the answer with Pro.

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`

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)`