Next Greater Element

Find the next greater element for each element in an array.

Language Selection

Choose your preferred programming language

Showing: Python

Next Greater Element

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.

Examples

Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

Example 2:

Input: nums1 = [2,4], nums2 = [1,2,3,4]
Output: [3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 2 is underlined in nums2 = [1,2,3,4]. The next greater element is 3.
- 4 is underlined in nums2 = [1,2,3,4]. There is no next greater element, so the answer is -1.

Example 3:

Input: nums1 = [1], nums2 = [1]
Output: [-1]
Explanation: The next greater element for 1 is -1.

Constraints

  • 1 <= nums1.length <= nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 10^4
  • All integers in nums1 and nums2 are unique.
  • All the integers of nums1 also appear in nums2.

Approach 1: Monotonic Stack (Optimal)

Algorithm

Use a monotonic stack to find the next greater element for each element in nums2.

Steps:

  1. Create a map to store next greater elements for each element in nums2
  2. Use a stack to maintain elements in decreasing order
  3. For each element in nums2:
    • While stack is not empty and current element > stack top:
      • Pop from stack and set next greater element
    • Push current element to stack
  4. For each element in nums1, return its next greater element from the map

Implementation

Python:

def nextGreaterElement(nums1, nums2):
    """
    Find next greater element using monotonic stack
    Time: O(n + m) where n = len(nums2), m = len(nums1)
    Space: O(n)
    """
    # Map to store next greater element for each element in nums2
    next_greater = {}
    stack = []
    
    # Process nums2 to find next greater elements
    for num in nums2:
        while stack and num > stack[-1]:
            next_greater[stack.pop()] = num
        stack.append(num)
    
    # Build result for nums1
    result = []
    for num in nums1:
        result.append(next_greater.get(num, -1))
    
    return result

Java:

import java.util.*;

class Solution {
    /**
     * Find next greater element using monotonic stack
     * Time: O(n + m) where n = nums2.length, m = nums1.length
     * Space: O(n)
     */
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // Map to store next greater element for each element in nums2
        Map<Integer, Integer> nextGreater = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
        
        // Process nums2 to find next greater elements
        for (int num : nums2) {
            while (!stack.isEmpty() && num > stack.peek()) {
                nextGreater.put(stack.pop(), num);
            }
            stack.push(num);
        }
        
        // Build result for nums1
        int[] result = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            result[i] = nextGreater.getOrDefault(nums1[i], -1);
        }
        
        return result;
    }
}

Go:

func nextGreaterElement(nums1 []int, nums2 []int) []int {
    /**
     * Find next greater element using monotonic stack
     * Time: O(n + m) where n = len(nums2), m = len(nums1)
     * Space: O(n)
     */
    // Map to store next greater element for each element in nums2
    nextGreater := make(map[int]int)
    stack := []int{}
    
    // Process nums2 to find next greater elements
    for _, num := range nums2 {
        for len(stack) > 0 && num > stack[len(stack)-1] {
            nextGreater[stack[len(stack)-1]] = num
            stack = stack[:len(stack)-1] // Pop
        }
        stack = append(stack, num)
    }
    
    // Build result for nums1
    result := make([]int, len(nums1))
    for i, num := range nums1 {
        if next, exists := nextGreater[num]; exists {
            result[i] = next
        } else {
            result[i] = -1
        }
    }
    
    return result
}

JavaScript:

/**
 * Find next greater element using monotonic stack
 * Time: O(n + m) where n = nums2.length, m = nums1.length
 * Space: O(n)
 */
function nextGreaterElement(nums1, nums2) {
    // Map to store next greater element for each element in nums2
    const nextGreater = new Map();
    const stack = [];
    
    // Process nums2 to find next greater elements
    for (const num of nums2) {
        while (stack.length > 0 && num > stack[stack.length - 1]) {
            nextGreater.set(stack.pop(), num);
        }
        stack.push(num);
    }
    
    // Build result for nums1
    const result = [];
    for (const num of nums1) {
        result.push(nextGreater.get(num) || -1);
    }
    
    return result;
}

C#:

using System.Collections.Generic;

public class Solution {
    /// <summary>
    /// Find next greater element using monotonic stack
    /// Time: O(n + m) where n = nums2.Length, m = nums1.Length
    /// Space: O(n)
    /// </summary>
    public int[] NextGreaterElement(int[] nums1, int[] nums2) {
        // Map to store next greater element for each element in nums2
        var nextGreater = new Dictionary<int, int>();
        var stack = new Stack<int>();
        
        // Process nums2 to find next greater elements
        foreach (int num in nums2) {
            while (stack.Count > 0 && num > stack.Peek()) {
                nextGreater[stack.Pop()] = num;
            }
            stack.Push(num);
        }
        
        // Build result for nums1
        int[] result = new int[nums1.Length];
        for (int i = 0; i < nums1.Length; i++) {
            result[i] = nextGreater.ContainsKey(nums1[i]) ? nextGreater[nums1[i]] : -1;
        }
        
        return result;
    }
}

Complexity Analysis

  • Time Complexity: O(n + m) - Process nums2 once and nums1 once
  • Space Complexity: O(n) - Stack and map storage

Key Insights

  1. Monotonic Stack: Maintain elements in decreasing order
  2. Next Greater Element: First element to the right that is greater
  3. Stack Property: Stack maintains decreasing order from bottom to top
  4. Efficient Processing: Process nums2 once, then lookup for nums1
  5. Map Storage: Store results for O(1) lookup

Edge Cases

  1. No Next Greater: Return -1 when no greater element exists
  2. Single Element: Handle arrays with single elements
  3. All Decreasing: Handle arrays where all elements are decreasing
  4. All Increasing: Handle arrays where all elements are increasing
  5. Duplicate Values: Handle arrays with duplicate values (not in this problem)

Test Cases

def test_nextGreaterElement():
    # Test case 1: Normal case
    nums1_1 = [4, 1, 2]
    nums2_1 = [1, 3, 4, 2]
    result1 = nextGreaterElement(nums1_1, nums2_1)
    expected1 = [-1, 3, -1]
    assert result1 == expected1
    
    # Test case 2: All increasing
    nums1_2 = [2, 4]
    nums2_2 = [1, 2, 3, 4]
    result2 = nextGreaterElement(nums1_2, nums2_2)
    expected2 = [3, -1]
    assert result2 == expected2
    
    # Test case 3: Single element
    nums1_3 = [1]
    nums2_3 = [1]
    result3 = nextGreaterElement(nums1_3, nums2_3)
    expected3 = [-1]
    assert result3 == expected3
    
    # Test case 4: All decreasing
    nums1_4 = [4, 3, 2]
    nums2_4 = [4, 3, 2, 1]
    result4 = nextGreaterElement(nums1_4, nums2_4)
    expected4 = [-1, -1, -1]
    assert result4 == expected4
    
    print("All tests passed!")

test_nextGreaterElement()

Follow-up Questions

  1. Next Greater Element II: Handle circular array?
  2. Next Greater Element III: Find next greater number with same digits?
  3. Next Greater Element with Distance: Find next greater element within k distance?
  4. Next Greater Element with Frequency: Handle duplicate values?
  5. Next Greater Element in BST: Find next greater element in binary search tree?

Common Mistakes

  1. Wrong Stack Order: Not maintaining decreasing order in stack
  2. Missing Map: Not storing results for efficient lookup
  3. Incorrect Indexing: Wrong array indexing in brute force approach
  4. Edge Case Handling: Not handling -1 case properly
  5. Time Complexity: Not optimizing from O(n*m) to O(n+m)

Interview Tips

  1. Start with Brute Force: Show understanding of the problem
  2. Optimize with Stack: Explain monotonic stack approach
  3. Handle Edge Cases: Mention -1 case and single element
  4. Discuss Trade-offs: Compare time vs space complexity
  5. Follow-up Ready: Be prepared for circular array and other variations

Concept Explanations

Next Greater Element: For each element, we need to find the first element to its right that is greater than it.

Monotonic Stack: A stack that maintains a specific order (in this case, decreasing order from bottom to top). This allows us to efficiently find the next greater element.

Stack Property: When we encounter a new element, we pop all elements from the stack that are smaller than the current element. This ensures the stack maintains decreasing order.

Why Stack Works: The stack helps us maintain the order of elements and efficiently find the next greater element without having to search through the entire array.

Map Storage: We use a map to store the next greater element for each element in nums2, so we can quickly lookup the result for each element in nums1.

Time Optimization: Instead of O(n*m) brute force, we achieve O(n+m) by processing nums2 once and then doing O(1) lookups for nums1.

Space Trade-off: We use O(n) extra space to achieve better time complexity, which is a common trade-off in algorithm optimization.