LeetFree - Leaked Interview questions from Google Facebook Amazon Microsoft LinkedIn

Question
Solution

You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1's elements in the corresponding places of nums2.

The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.

Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]
Explanation:
    For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
    For number 1 in the first array, the next greater number for it in the second array is 3.
    For number 2 in the first array, there is no next greater number for it in the second array, so output -1.

Example 2:

Input: nums1 = [2,4], nums2 = [1,2,3,4].
Output: [3,-1]
Explanation:
    For number 2 in the first array, the next greater number for it in the second array is 3.
    For number 4 in the first array, there is no next greater number for it in the second array, so output -1.

Note:

All elements in nums1 and nums2 are unique.
The length of both nums1 and nums2 would not exceed 1000.

Summary
Solution
\n

Summary

You are given two arrays (without duplicates) $findNums$ and $nums$ where $findNums$ \xe2\x80\x99s elements are subset of $nums$ .Find all the\nnext greater\nnumbers for $findNums$ \'s elements in the corresponding places of $nums$ .

The Next Greater Number of a number x in $findNums$ is the first greater number to its right in $nums$ . If it does not exist, output -1 for\nthis number.

Solution

Approach #1 Brute Force [Accepted]

In this method, we pick up every element of the $findNums$ array(say $findNums[i]$ ) and then search for its own occurence in the $nums$ array(which is\n indicated by setting $found$ to True). After this, we look linearly for a number in $nums$ which is greater than $findNums[i]$ , which\n is also added to the $res$ array to be returned. If no such element is found, we put a $\\text{-1}$ at the corresponding location.

\n\n

Complexity Analysis

Time complexity : $O(m*n)$ . The complete $nums$ array(of size $n$ ) needs to be scanned for all the $m$ elements of $findNums$ in\n the worst case.
Space complexity : $O(m)$ . $res$ array of size $m$ is used, where $m$ is the length of $findNums$ array.

Approach #2 Better Brute Force [Accepted]

Instead of searching for the occurence of $findNums[i]$ linearly in the $nums$ array, we can make use of a hashmap $hash$ to store\nthe elements of $nums$ in the form of $(element, index)$ . By doing this, we can find $findNums[i]$ \'s index in $nums$ array directly and\nthen continue to search for the next larger element in a linear fashion.

\n\n

Complexity Analysis

\n
Time complexity : $O(m*n)$ . The whole $nums$ array, of length $n$ needs to be scanned for all the $m$ elements of $finalNums$ in the worst case.
\n
\n
Space complexity : $O(m)$ . $res$ array of size $m$ is used. A hashmap $hash$ of size $m$ is used, where $m$ refers to the\n length of the $findNums$ array.
\n

Approach #3 Using Stack [Accepted]

In this approach, we make use of pre-processing first so as to make the results easily available later on.\n We make use of a stack( $stack$ ) and a hashmap( $map$ ). $map$ is used to store the result for every posssible number in $nums$ in\nthe form of $(element, next\\_greater\\_element)$ . Now, we look at how to make entries in $map$ .

We iterate over the $nums$ array\nfrom the left to right. We push every element $nums[i]$ on the stack if it is less than the previous element on the top of the stack\n( $stack[top]$ ). No entry is made in $map$ for such $nums[i]\'s$ right now. This happens because\nthe $nums[i]\'s$ encountered so far are coming in a descending order.

If we encounter an element $nums[i]$ such that $nums[i] > stack[top]$ , we keep on popping all the elements\nfrom $stack[top]$ until we encounter $stack[k]$ such that $stack[k] &leq; nums[i]$ . For every element popped out of the stack\n $stack[j]$ , we put the popped element along with its next greater number(result) into the hashmap $map$ , in the form\n $(stack[j], nums[i])$ . Now, it is obvious that the\nnext greater element for all elements $stack[j]$ , such that $k < j ≤ top$ is $nums[i]$ (since this larger element caused all the\n $stack[j]$ \'s to be popped out). We stop popping the elements at $stack[k]$ because this $nums[i]$ can\'t act as the next greater element\nfor the next elements on the stack.

Thus, an element is popped out of the stack whenever a next greater element is found for it. Thus, the elements remaining in the stack are the\nones for which no next greater element exists in the $nums$ array. Thus, at the end of the iteration over $nums$ , we pop the remaining\nelements from the $stack$ and put their entries in $hash$ with a $\\text{-1}$ as their corresponding results.

Then, we can simply iterate over the $findNums$ array to find the corresponding results from $map$ directlhy.

The following animation makes the method clear:

!?!../Documents/496_Next_Greater_Element_I.json:1280,720!?!

\n\n

Complexity Analysis

\n
Time complexity : $O(m+n)$ . The entire $nums$ array(of size $n$ ) is scanned only once. The stack\'s $n$ elements are popped\n only once. The $findNums$ array is also scanned only once.
\n
\n
Space complexity : $O(m+n)$ . $stack$ and $map$ of size $n$ is used. $res$ array of size $m$ is used, where $n$ refers to the\n length of the $nums$ array and $m$ refers to the length of the $findNums$ array.
\n

Analysis written by: @vinod23

496. Next Greater Element I

Summary

Solution

Approach #1 Brute Force [Accepted]

Approach #2 Better Brute Force [Accepted]

Approach #3 Using Stack [Accepted]