Next Greater Element I

Published at23 Jul 2026

Stack Easy 1 views

Like0

You are given two arrays nums1 and nums2 where nums1 is a subset of nums2. For each element in nums1, find its next greater element in nums2. The next greater element is the first element to the right that is strictly greater. If none exists, the answer is -1.

A monotonic decreasing stack on nums2 precomputes the next greater element for every value. As you iterate through nums2, push each element onto the stack. When the current element is greater than the top of the stack, pop and record the mapping. After processing all of nums2, use the map to look up answers for each element in nums1.This problem introduces the monotonic stack concept in its simplest form. Unlike the full Next Greater Element problem, this version only asks about a subset of values, making it more approachable.The hash map combined with a monotonic stack is a common pattern. The stack finds the next greater for every element in nums2, and the map stores the results for O(1) lookup when building the answer for nums1.If nums2 contains duplicate values, be careful not to overwrite existing mappings. The first occurrence of a value should keep its next greater element.

Example Input & Output

Example 1

Input

nums1=[1,3,2], nums2=[1,2,3,1]

Output

[2,-1,3]

Explanation

1 next greater: 2. 3 next greater: none. 2 next greater: 3.

Example 2

Input

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

Output

[3,-1]

Explanation

2's NGE: 3. 4's NGE: none.

Example 3

Input

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

Output

[-1,3,-1]

Explanation

4's NGE: none. 1's NGE: 3. 2's NGE: none.

Algorithm Flow

Recommendation Algorithm Flow for Next Greater Element I

Solution Approach

Create a hash map and an empty stack. Iterate through nums2. For each value, while the stack is not empty and the current value is greater than the top, pop and record the mapping. Push the current value. After the loop, remaining values in the stack have no next greater (map to -1). Build the result using the map for each element in nums1.

Time complexity is O(n). Space complexity is O(n).

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

java

import java.util.*;
class Solution {
    public int[] solution(int[] nums1, int[] nums2) {
        Map<Integer,Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
        for (int val : nums2) {
            while (!stack.isEmpty() && val > stack.peek()) {
                int popped = stack.pop();
                if (!map.containsKey(popped)) map.put(popped, val);
            }
            stack.push(val);
        }
        while (!stack.isEmpty()) { int v = stack.pop(); if (!map.containsKey(v)) map.put(v, -1); }
        int[] result = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) result[i] = map.get(nums1[i]);
        return result;
    }
}

javascript

function solution(nums1, nums2) {
  var map = {};
  var stack = [];
  for (var i = 0; i < nums2.length; i++) {
    var val = nums2[i];
    while (stack.length && val > stack[stack.length - 1]) {
      var popped = stack.pop();
      if (!(popped in map)) map[popped] = val;
    }
    stack.push(val);
  }
  while (stack.length) { var v = stack.pop(); if (!(v in map)) map[v] = -1; }
  var result = [];
  for (var i = 0; i < nums1.length; i++) result.push(map[nums1[i]]);
  return result;
}

php

<?php
function solution($nums1, $nums2) {
    $map = [];
    $stack = [];
    foreach ($nums2 as $val) {
        while (!empty($stack) && $val > end($stack)) {
            $popped = array_pop($stack);
            if (!isset($map[$popped])) $map[$popped] = $val;
        }
        array_push($stack, $val);
    }
    foreach ($stack as $v) { if (!isset($map[$v])) $map[$v] = -1; }
    $result = [];
    foreach ($nums1 as $x) $result[] = $map[$x];
    return $result;
}

python

def solution(nums1, nums2):
    nge = {}
    stack = []
    for val in nums2:
        while stack and val > stack[-1]:
            popped = stack.pop()
            if popped not in nge:
                nge[popped] = val
        stack.append(val)
    for val in stack:
        if val not in nge:
            nge[val] = -1
    return [nge[x] for x in nums1]

rust

use std::collections::HashMap;
fn solution(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
    let mut map = HashMap::new();
    let mut stack: Vec<i32> = Vec::new();
    for &val in &nums2 {
        while let Some(&top) = stack.last() {
            if val <= top { break; }
            let popped = stack.pop().unwrap();
            if !map.contains_key(&popped) { map.insert(popped, val); }
        }
        stack.push(val);
    }
    for v in &stack { if !map.contains_key(v) { map.insert(*v, -1); } }
    nums1.iter().map(|x| *map.get(x).unwrap_or(&-1)).collect()
}

typescript

function solution(nums1: number[], nums2: number[]): number[] {
    var map: any = {};
    var stack: number[] = [];
    for (var i = 0; i < nums2.length; i++) {
        var val = nums2[i];
        while (stack.length && val > stack[stack.length - 1]) {
            var popped = stack.pop() as number;
            if (!(popped in map)) map[popped] = val;
        }
        stack.push(val);
    }
    while (stack.length) { var v = stack.pop() as number; if (!(v in map)) map[v] = -1; }
    var result: number[] = [];
    for (var i = 0; i < nums1.length; i++) result.push(map[nums1[i]]);
    return result;
}

Related Stack Challenges

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this Challenge.

Next Greater Element I

Example Input & Output

Algorithm Flow

Solution Approach

Best AnswersThese are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

Solutions Coming Soon

Related Stack Challenges

Decode String

Remove All Adjacent Duplicates in String

Basic Calculator II

Largest Rectangle in Histogram

Trapping Rain Water

Longest Valid Parentheses

Comments (0)

Join the Discussion

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.