Next Greater Element I

Published at23 Jul 2026

Stack Easy 0 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.

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.

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])
      map[stack.pop()] = val
    stack.push(val)
  }
  while (stack.length) map[stack.pop()] = -1
  return nums1.map(function(x) { return map[x] })
}

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

Gallery Stock Order Check

Harbor Cargo Lineup

Warehouse Crate Ordering

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.