496. Next Greater Element I

Next Greater Element I (LeetCode 496) is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Stack Patterns pattern, in the Monotonic Stack subpattern.

How to solve Next Greater Element I

Next Greater Element I is a Monotonic Stack problem, part of Stack Patterns. Master monotonic stack for next greater element, daily temperatures, and stock span problems.

Work towards the solution in these steps:

1. Consider which data structure can help efficiently find the next greater element for each number by allowing you to process elements in a single pass.
2. Think about maintaining a stack of numbers in a way that the elements are in decreasing order, so you can quickly find the next greater element when a larger number appears.
3. While iterating through nums2, use the stack to keep track of elements that haven't found their next greater element yet; when you encounter a bigger number, pop from the stack and record this as the next greater for those popped elements.

The reference solution runs in O(N + M) time and O(N) space.

The Next Greater Element I solution and editorial walks through the full approach with reference code.

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?

Topics and companies

Topics: Array, Hash Table, Stack, Monotonic Stack.

Reported in interviews at Amazon, Microsoft.

How to practise Next Greater Element I on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(N + M) time and O(N) space.

Open Next Greater Element I in the code editor, or read the Next Greater Element I editorial for a worked solution with its approach and complexity analysis.

Where Next Greater Element I sits in the DSA pattern sheet

• Stack Patterns pattern guide
• Monotonic Stack subpattern
• The full DSA patterns sheet

Problems related to Next Greater Element I

Other problems that use the same Monotonic Stack and Stack Patterns techniques:

• Car Fleet — Medium, same subpattern
• Daily Temperatures — Medium, same subpattern
• Final Prices With a Special Discount in a Shop — Easy, same subpattern
• Find the Most Competitive Subsequence — Medium, same subpattern
• Maximum Width Ramp — Medium, same subpattern
• Next Greater Element II — Medium, same subpattern

Next Greater Element I FAQ