How to Solve Next Greater Element I

In the Next Greater Element I problem, you're tasked with finding the next greater element for each number in nums1 from the nums2 array. This can be achieved using an efficient combination of array scanning, hash lookup, and stacks, significantly improving performance compared to a naive approach.

Problem Statement

You are given two integer arrays, nums1 and nums2, where nums1 is a subset of nums2. The task is to find the next greater element for each element in nums1, which refers to the first element that is greater and appears to the right of that element in nums2. If no greater element exists, the result should be -1.

For each element in nums1, you must identify its position in nums2 and find the next greater element to the right. If no such element exists, return -1. An efficient solution involves array scanning and hash lookups, avoiding a brute force method that would be too slow.

Examples

Example 1

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

Output: [-1,3,-1]

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]

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.

Solution Approach

Stack-based Monotonic Approach

A monotonic stack approach can be used to find the next greater elements efficiently. Traverse nums2 from right to left, using the stack to keep track of the next greater elements for the current element. Each element is processed once, allowing for a time complexity of O(n), where n is the length of nums2.

Hash Table Lookup

After processing nums2 with the stack, use a hash table to map each element in nums2 to its next greater element. This allows you to efficiently look up the next greater element for each number in nums1 in constant time, reducing the overall time complexity of the solution.

Final Result Construction

With the hash table ready, iterate through nums1 and for each element, retrieve its next greater element from the table. If no greater element exists, append -1. This step ensures that the solution works in O(m) time, where m is the length of nums1.

Complexity Analysis

The overall time complexity is O(n + m), where n is the length of nums2 and m is the length of nums1. The space complexity is O(n) due to the hash table and stack.

What Interviewers Usually Probe

• Candidates should be able to explain how the stack is used to maintain the next greater elements in a monotonic manner.
• Look for a clear understanding of how hash tables optimize the lookup process after processing nums2.
• Candidates should discuss the time and space complexities and how they are optimized compared to a brute-force solution.

Common Pitfalls or Variants

Common pitfalls

• Not using the stack to maintain the next greater elements in a monotonic order, which leads to a less efficient solution.
• Overlooking the need to map elements of nums2 to their next greater element using a hash table, leading to slower lookups.
• Misunderstanding the problem constraints, leading to inefficient or incorrect handling of array indices.

Follow-up variants

• Handling multiple queries for different nums1 arrays with the same nums2 array.
• Optimizing further using additional data structures, like trees or heaps, to support different types of range queries.
• Adapting the approach for finding the previous greater element instead of the next greater element.

How GhostInterview Helps

• GhostInterview helps you quickly implement the monotonic stack approach and optimize the time complexity.
• With GhostInterview, you can test your solution against a variety of edge cases, ensuring robustness.
• GhostInterview’s detailed feedback helps pinpoint inefficiencies in your solution, especially with respect to array scanning and hash lookups.

Topic Pages

• Array
• Hash Table
• Stack
• Monotonic Stack

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the time complexity of the Next Greater Element I problem?

The time complexity is O(n + m), where n is the length of nums2 and m is the length of nums1, due to the stack processing and hash table lookups.

How can the stack be used in the Next Greater Element I problem?

The stack is used to store elements of nums2 while traversing it from right to left, ensuring that we can find the next greater element for each item in constant time.

What is the role of the hash table in solving Next Greater Element I?

The hash table stores the next greater element for each element in nums2, allowing for constant time lookup when processing nums1.

How does the space complexity of this solution compare to other approaches?

The space complexity is O(n), where n is the length of nums2, due to the stack and hash table. This is efficient compared to a brute-force approach, which would require O(m * n) space.

Can this solution be adapted for similar problems?

Yes, this approach can be adapted to solve similar problems, such as finding the previous greater element or handling different types of range queries.