Next Greater Element I solution and explanation
Google
TCS
9 more videos on this problem
Next Greater Element I - Leetcode 496 - PythonNeetCode · 14:53 · 123K views
Next Greater Element 1 (LeetCode 496) | Full solution with examples and animation | Study AlgorithmsNikhil Lohia · 15:01 · 65K views
LeetCode Next Greater Element I Solution Explained - JavaNick White · 9:51 · 37K views
LeetCode 496: Next Greater Element IEngineering Digest · 12:56 · 10K views
Next Greater Element I - LeetCode 496 | Stop Overthinking, Try ThisCodingNinja · 12:25 · 1K views
LeetCode 496. Next Greater Element I Explanation and Solutionhappygirlzt · 9:06 · 1K views
LeetCode 496 : Next Greater Element I || EASY || JAVA || Detailed SolutionCodeGPT · 9:47 · 965 views
496. Next Greater Element I || LEETCODE SOLUTION IN C++ || DATA STRUCTURE AND ALGOAbhishweta Gupta · 2:24 · 713 views
Next Greater Element I | Leetcode 496 | Graviton SchoolGravitonSchool · 17:00 · 484 views
Leetcode 496 - Next Greater Element I (JAVA Solution Explained!)LC Bear · 17:49 · 444 views
The problem
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.
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.
Constraints:
1 <= nums1.length <= nums2.length <= 10000 <= nums1[i], nums2[i] <= 104- All integers in
nums1andnums2are unique. - All the integers of
nums1also appear innums2.
O(nums1.length + nums2.length) solution?Approach overview
Problem Overview: You are given two arrays, nums1 and nums2, where every element of nums1 appears in nums2. For each element in nums1, find the first greater number to its right in nums2. If no greater value exists, return -1. The challenge is efficiently locating the next greater element without repeatedly scanning the entire array.
Approach 1: Brute Force Scan (Time: O(n*m), Space: O(1))
Start by locating each element of nums1 inside nums2. Once found, iterate to the right of that position until you encounter a larger value. If a larger value appears, record it as the answer; otherwise return -1. This approach uses simple iteration over the array but repeatedly scans portions of nums2, which leads to quadratic behavior in the worst case. It works for small inputs and is useful for understanding the core requirement: scanning to the right for a larger element.
Approach 2: Monotonic Stack + Hash Map (Time: O(n + m), Space: O(n))
The optimized solution preprocesses nums2 using a monotonic stack. Traverse nums2 from left to right while maintaining a decreasing stack. When the current number is greater than the stack’s top element, pop elements from the stack and record their next greater value in a hash table. This means you discovered the first larger number to their right. Push the current element onto the stack and continue scanning.
After processing the entire array, the hash map stores the next greater value for every relevant number in nums2. Elements left in the stack have no greater element, so their result remains -1. Finally, iterate through nums1 and perform constant-time hash lookups to retrieve the precomputed answers. Each element is pushed and popped at most once from the stack, giving linear complexity.
The key insight is preprocessing the larger array so queries become constant-time lookups. Instead of repeatedly searching to the right, the stack identifies next-greater relationships in a single pass.
Recommended for interviews: Interviewers expect the monotonic stack solution. The brute force method demonstrates you understand the problem but does not scale well. Recognizing that this is a classic “next greater element” pattern and solving it with a decreasing stack shows strong pattern recognition and familiarity with stack-based array processing.
Approach 1: Brute Force Approach
This approach involves iterating over each element of nums1 and finding the corresponding element in nums2. Once located, search for the next greater element to its right. This straightforward method checks each pair and ensures correctness but may not be optimal for larger arrays.
def next_greater_element(nums1, nums2):
result = []
for num in nums1:
try:
index = nums2.index(num)
greater = -1
for n in nums2[index + 1:]:
if n > num:
greater = n
break
result.append(greater)
except ValueError:
result.append(-1)
return result
nums1 = [4, 1, 2]
nums2 = [1, 3, 4, 2]
print(next_greater_element(nums1, nums2))import java.util.*;
public class NextGreaterElement {
public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
int[] result = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) {
int j = 0;
while (j < nums2.length && nums2[j] != nums1[i]) j++;
int k = j + 1;
while (k < nums2.length && nums2[k] <= nums1[i]) k++;
result[i] = (k < nums2.length) ? nums2[k] : -1;
}
return result;
}
public static void main(String[] args) {
int[] nums1 = {4, 1, 2};
int[] nums2 = {1, 3, 4, 2};
System.out.println(Arrays.toString(nextGreaterElement(nums1, nums2)));
}
}#include <iostream>
#include <vector>
using namespace std;
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
vector<int> res;
for (int i = 0; i < nums1.size(); ++i) {
int j = 0;
while (j < nums2.size() && nums2[j] != nums1[i]) ++j;
int k = j + 1;
while (k < nums2.size() && nums2[k] <= nums1[i]) ++k;
res.push_back(k < nums2.size() ? nums2[k] : -1);
}
return res;
}
int main() {
vector<int> nums1 = {4, 1, 2};
vector<int> nums2 = {1, 3, 4, 2};
vector<int> result = nextGreaterElement(nums1, nums2);
for (int num : result) {
cout << num << " ";
}
return 0;
}function nextGreaterElement(nums1, nums2) {
let result = [];
nums1.forEach(num1 => {
let index = nums2.indexOf(num1);
let nextGreater = -1;
for (let i = index + 1; i < nums2.length; i++) {
if (nums2[i] > num1) {
nextGreater = nums2[i];
break;
}
}
result.push(nextGreater);
});
return result;
}
let nums1 = [4, 1, 2];
let nums2 = [1, 3, 4, 2];
console.log(nextGreaterElement(nums1, nums2));#include <stdio.h>
#include <stdlib.h>
int* nextGreaterElement(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
int* result = (int*)malloc(nums1Size * sizeof(int));
*returnSize = nums1Size;
for(int i = 0; i < nums1Size; ++i) {
int found = 0, j;
for(j = 0; j < nums2Size; ++j) {
if(nums2[j] == nums1[i]) {
found = 1;
break;
}
}
if(found) {
int nextGreater = -1;
for(j = j + 1; j < nums2Size; ++j) {
if(nums2[j] > nums1[i]) {
nextGreater = nums2[j];
break;
}
}
result[i] = nextGreater;
}
}
return result;
}
int main() {
int nums1[] = {4, 1, 2};
int nums2[] = {1, 3, 4, 2};
int returnSize;
int* result = nextGreaterElement(nums1, 3, nums2, 4, &returnSize);
for (int i = 0; i < returnSize; ++i) {
printf("%d ", result[i]);
}
free(result);
return 0;
}using System;
using System.Collections.Generic;
public class NextGreaterElementProblem {
public int[] NextGreaterElement(int[] nums1, int[] nums2) {
int[] result = new int[nums1.Length];
for (int i = 0; i < nums1.Length; i++) {
int pos = Array.IndexOf(nums2, nums1[i]);
int greater = -1;
for (int j = pos + 1; j < nums2.Length; j++) {
if (nums2[j] > nums1[i]) {
greater = nums2[j];
break;
}
}
result[i] = greater;
}
return result;
}
public static void Main() {
int[] nums1 = { 4, 1, 2 };
int[] nums2 = { 1, 3, 4, 2 };
var obj = new NextGreaterElementProblem();
int[] answer = obj.NextGreaterElement(nums1, nums2);
Console.WriteLine(string.Join(", ", answer));
}
}This Python script applies a brute force method, iterating each num1 element through nums2 to locate the element and find a subsequent greater number. It leverages Python's list slicing and exception handling for cleaner code execution.
The time complexity is O(n * m) and space is O(1) outside of the results maintained.
Approach 2: Optimized Stack and Hashmap Approach
This approach utilizes a stack and a hashmap to efficiently solve the problem. As we traverse nums2, we use the stack to store elements for which the next greater element hasn't been found yet. Whenever a greater element is found, it's recorded in the hashmap against the elements in the stack. This technique is optimal and runs in linear time.
def next_greater_element(nums1, nums2):
hashmap = {}
stack = []
for num in nums2:
while stack and stack[-1] < num:
hashmap[stack.pop()] = num
stack.append(num)
return [hashmap.get(num, -1) for num in nums1]
nums1 = [4, 1, 2]
nums2 = [1, 3, 4, 2]
print(next_greater_element(nums1, nums2))import java.util.*;
public class NextGreaterElementOpt {
public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
Map<Integer, Integer> map = new HashMap<>();
Stack<Integer> stack = new Stack<>();
for (int num : nums2) {
while (!stack.isEmpty() && stack.peek() < num) {
map.put(stack.pop(), num);
}
stack.push(num);
}
int[] result = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) {
result[i] = map.getOrDefault(nums1[i], -1);
}
return result;
}
public static void main(String[] args) {
int[] nums1 = {4, 1, 2};
int[] nums2 = {1, 3, 4, 2};
System.out.println(Arrays.toString(nextGreaterElement(nums1, nums2)));
}
}#include <iostream>
#include <unordered_map>
#include <stack>
#include <vector>
using namespace std;
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> m;
stack<int> s;
for (int num : nums2) {
while (!s.empty() && s.top() < num) {
m[s.top()] = num;
s.pop();
}
s.push(num);
}
vector<int> result;
for (int num : nums1) {
result.push_back(m.count(num) ? m[num] : -1);
}
return result;
}
int main() {
vector<int> nums1 = {4, 1, 2};
vector<int> nums2 = {1, 3, 4, 2};
vector<int> result = nextGreaterElement(nums1, nums2);
for (int num : result) {
cout << num << " ";
}
return 0;
}function nextGreaterElement(nums1, nums2) {
let map = new Map();
let stack = [];
nums2.forEach(num => {
while (stack.length && stack[stack.length - 1] < num) {
map.set(stack.pop(), num);
}
stack.push(num);
});
return nums1.map(num => map.get(num) || -1);
}
let nums1 = [4, 1, 2];
let nums2 = [1, 3, 4, 2];
console.log(nextGreaterElement(nums1, nums2));#include <stdio.h>
#include <stdlib.h>
#define SIZE 10000
struct Stack {
int top;
int items[SIZE];
};
void push(struct Stack* s, int x) {
s->items[++s->top] = x;
}
int pop(struct Stack* s) {
return s->items[s->top--];
}
int isEmpty(struct Stack* s) {
return s->top == -1;
}
int* nextGreaterElement(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
int* result = (int*)malloc(nums1Size * sizeof(int));
*returnSize = nums1Size;
int map[SIZE];
for (int i = 0; i < SIZE; i++) {
map[i] = -1;
}
struct Stack s;
s.top = -1;
for (int i = 0; i < nums2Size; i++) {
while (!isEmpty(&s) && s.items[s.top] < nums2[i]) {
map[s.items[s.top]] = nums2[i];
pop(&s);
}
push(&s, nums2[i]);
}
for (int i = 0; i < nums1Size; i++) {
result[i] = map[nums1[i]];
}
return result;
}
int main() {
int nums1[] = {4, 1, 2};
int nums2[] = {1, 3, 4, 2};
int returnSize;
int* result = nextGreaterElement(nums1, 3, nums2, 4, &returnSize);
for (int i = 0; i < returnSize; ++i) {
printf("%d ", result[i]);
}
free(result);
return 0;
}using System;
using System.Collections.Generic;
public class NextGreaterElementOptimized {
public int[] NextGreaterElement(int[] nums1, int[] nums2) {
Dictionary<int, int> map = new Dictionary<int, int>();
Stack<int> stack = new Stack<int>();
foreach (int num in nums2) {
while (stack.Count > 0 && stack.Peek() < num) {
map[stack.Pop()] = num;
}
stack.Push(num);
}
for (int i = 0; i < nums1.Length; i++) {
nums1[i] = map.ContainsKey(nums1[i]) ? map[nums1[i]] : -1;
}
return nums1;
}
public static void Main() {
int[] nums1 = { 4, 1, 2 };
int[] nums2 = { 1, 3, 4, 2 };
var obj = new NextGreaterElementOptimized();
int[] result = obj.NextGreaterElement(nums1, nums2);
Console.WriteLine(string.Join(", ", result));
}
}Using both stack and hashmap, this Python solution processes nums2 entirely, updating the hashmap with the next greater elements as soon as they are found. The transformation into nums1 results is rapid due to pre-built mappings.
The procedure ensures O(n + m) time complexity with O(m) space due to hashmap size determined by nums2 length.
Approach 3: Monotonic Stack
We can traverse the array nums2 from right to left, maintaining a stack stk that is monotonically increasing from top to bottom. We use a hash table d to record the next greater element for each element.
When we encounter an element x, if the stack is not empty and the top element of the stack is less than x, we keep popping the top elements until the stack is empty or the top element is greater than or equal to x. At this point, if the stack is not empty, the top element of the stack is the next greater element for x. Otherwise, x has no next greater element.
Finally, we traverse the array nums1 and use the hash table d to get the answer.
The time complexity is O(m + n), and the space complexity is O(n). Here, m and n are the lengths of the arrays nums1 and nums2, respectively.
function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
const stk: number[] = [];
const d: Record<number, number> = {};
for (const x of nums2.reverse()) {
while (stk.length && stk.at(-1)! < x) {
stk.pop();
}
d[x] = stk.length ? stk.at(-1)! : -1;
stk.push(x);
}
return nums1.map(x => d[x]);
}func nextGreaterElement(nums1 []int, nums2 []int) (ans []int) {
stk := []int{}
d := map[int]int{}
for i := len(nums2) - 1; i >= 0; i-- {
x := nums2[i]
for len(stk) > 0 && stk[len(stk)-1] < x {
stk = stk[:len(stk)-1]
}
if len(stk) > 0 {
d[x] = stk[len(stk)-1]
}
stk = append(stk, x)
}
for _, x := range nums1 {
if v, ok := d[x]; ok {
ans = append(ans, v)
} else {
ans = append(ans, -1)
}
}
return
}use std::collections::HashMap;
impl Solution {
pub fn next_greater_element(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
let mut stk = Vec::new();
let mut d = HashMap::new();
for &x in nums2.iter().rev() {
while let Some(&top) = stk.last() {
if top <= x {
stk.pop();
} else {
break;
}
}
if let Some(&top) = stk.last() {
d.insert(x, top);
}
stk.push(x);
}
nums1
.into_iter()
.map(|x| *d.get(&x).unwrap_or(&-1))
.collect()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | The time complexity is O(n * m) and space is O(1) outside of the results maintained. |
| Optimized Stack and Hashmap Approach | The procedure ensures O(n + m) time complexity with O(m) space due to hashmap size determined by nums2 length. |
| Monotonic Stack | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Scan | O(n * m) | O(1) | Simple baseline solution or when input sizes are very small |
| Monotonic Stack + Hash Map | O(n + m) | O(n) | General case and interview-preferred approach for next greater element problems |
Frequently asked questions
Is Next Greater Element I easy or hard?
Next Greater Element I is classified as an Easy problem on LeetCode. The brute force solution is straightforward, but recognizing the monotonic stack pattern is the key step that prepares you for more advanced stack-based array problems.
Next Greater Element I Python/Java solution
Python and Java implementations typically use a stack to process nums2 and a HashMap or dictionary to store next greater mappings. After building the map in O(n), iterate through nums1 and retrieve answers directly from the map.
How to solve Next Greater Element I in O(n)?
Process nums2 using a monotonic decreasing stack. While scanning the array, pop smaller elements when a larger number appears and store the mapping in a hash map. After preprocessing, answer each nums1 query with constant-time lookups from the map.
What is the best approach for Next Greater Element I?
The best approach uses a monotonic decreasing stack combined with a hash map. You preprocess nums2 and compute the next greater value for each element while scanning once. This reduces repeated searches and achieves O(n + m) time complexity with O(n) extra space.
Is Next Greater Element I asked at Google/Amazon/Meta?
Next Greater Element I represents a classic monotonic stack pattern frequently used in technical interviews. Variations of the problem appear at companies like Amazon, Google, and Meta, especially in problems involving next greater or next smaller elements in arrays.
What data structure is used in Next Greater Element I?
The optimal solution uses a stack (specifically a monotonic decreasing stack) along with a hash table for fast lookups. The stack helps determine the next greater element efficiently while the hash map stores the computed results.
What is the time complexity of Next Greater Element I?
The optimal monotonic stack solution runs in O(n + m) time, where n is the length of nums2 and m is the length of nums1. Each element in nums2 is pushed and popped from the stack at most once, making the scan linear.