Skip to main content
Talentd

Next Greater Element I - Solution & Explanation

EasyArrayHash TableStackMonotonic Stack21 min readAsked at: Amazon, Microsoft, Apple +14
Practice this problem

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.

 

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 <= 1000
  • 0 <= nums1[i], nums2[i] <= 104
  • All integers in nums1 and nums2 are unique.
  • All the integers of nums1 also appear in nums2.

 

Follow up: Could you find an 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.

This C solution uses nested looping to find the next greater element by directly comparing elements. The outer loop iterates through nums1, and for each element, it finds its position in nums2 using another loop. Then, it looks for the next greater element from that position. Although simple, this solution can be improved in terms of efficiency.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity of this brute force approach is O(n * m), where n is the number of elements in nums1, and m is the number of elements in nums2. The space complexity is O(1) apart from the output array.

Try this approach in the editor →

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.

This C solution builds an efficient resolution using a combination of a stack and hashmap. As elements traverse, unmatched elements are pushed onto the stack. When a larger element appears, it is stored in the hashmap mapped to the popped stack elements. This efficient solution runs in O(n) where n is nums2.length.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity is O(n + m), approaching linear time with respect to input size and space is approximately O(m) for hashmap tracking.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

The time complexity of this brute force approach is O(n * m), where n is the number of elements in nums1, and m is the number of elements in nums2. The space complexity is O(1) apart from the output array.

Optimized Stack and Hashmap Approach

The time complexity is O(n + m), approaching linear time with respect to input size and space is approximately O(m) for hashmap tracking.

Monotonic Stack—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force ScanO(n * m)O(1)Simple baseline solution or when input sizes are very small
Monotonic Stack + Hash MapO(n + m)O(n)General case and interview-preferred approach for next greater element problems

Video Solution

Next Greater Element I - Leetcode 496 - Python • NeetCode • 123,725 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Next Greater Element I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Daily Temperatures

Next

Next Greater Element II