Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Next Greater Element

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.

2

.....

.....

.....

Like the course? Get enrolled and start learning!
K

karrad

· 3 years ago

  • Input: nums1 = [9,7,1], nums2 = [1,7,9,5,4,3]
  • Output: [-1,9,7]

In this example, we first take 9 and compare to every number to right of 9 in nums2. No number >9 so -1

Then 7. The 1st number to right of 7 (i.e only consider last 4 numbers in nums2) is 9

Now we consider 1. If we go by the same logic, we should only consider 5,4,3 in nums2. Why is the answer 7? Should it not be 5?

Thanks

M

Show 2 replies
Kinshuk Agrawal

Kinshuk Agrawal

· 2 years ago

It would be nice to have such a comprehensive explanation + pseudo code for every pattern

A

Anand Mohan

· 3 years ago

There seems to be a mistake in the image. We are using monotonically decreasing stack.