Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Next Greater Element
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

Given two integer arrays nums1 and nums2, return an array answer such that answer[i] is the next greater number for every nums1[i] in nums2.

The next greater element for an element x is the first element to the right of x that is greater than x. If there is no greater number, output -1 for that number.

The numbers in nums1 are all present in nums2.

Examples

    • Input: nums1 = [4,2,6], nums2 = [6,2,4,5,3,7]
    • Output: [5,4,7]
    • Explanation: The next greater number for 4 is 5, for 2 is 4, and for 6 is 7 in nums2.
    • Input: nums1 = [9,7,1], nums2 = [1,7,9,5,4,3]
    • Output: [-1,9,7]
    • Explanation: The next greater number for 9 does not exist, for 7 is 9, and for 1 is 7 in nums2.
    • Input: nums1 = [5,12,3], nums2 = [12,3,5,4,10,15]
    • Output: [10,15,5]
    • Explanation: The next greater number for 5 is 10, for 12 is 15, and for 3 is 4 in nums2.

Constraints:

  • 1 <= nums1.length <= nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 10<sup>4</sup>
  • All integers in nums1 and nums2 are unique.
  • All the integers of nums1 also appear in nums2.

Solution

This problem requires us to find the next greater element for each element in nums1 by searching nums2. The output array contains either the next greater element or -1 if no such element exists.

This problem can be solved using a Monotonic Stack and Hashmap. The Monotonic Stack helps to find the next greater element for each element in nums2. The Hashmap then maps each element to its next greater element.

Algorithm Walkthrough

  1. Initialize an empty stack and an empty hashmap.
  2. Loop through the nums2 array from left to right.
  3. For each number in nums2, while the stack is not empty and the current number is greater than the top element of the stack:
    • Pop the element from the stack and add an entry to the hashmap with the popped element as the key and the current number as the value.
  4. Push the current number onto the stack.
  5. After the loop, any numbers remaining on the stack do not have a next greater element, so for each of these numbers, add an entry to the hashmap with the number as the key and -1 as the value.
  6. Finally, create an output array by mapping each number in nums1 to its corresponding value in the hashmap.
Next Greater Element through Monotonically Decreasing Stack
Next Greater Element through Monotonically Decreasing Stack

Code

Here is the code for this algorithm:

Python3
Python3
. . . .

Time and Space Complexity

The time complexity of this algorithm is O(N), where N is the length of nums2, since each element is pushed and popped from the stack exactly once. The space complexity is O(N) as well, due to the additional space needed for the stack and the hashmap.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible