## 496. Next Greater Element I

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:

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

b'
\n\n

## Summary

\n

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

\n

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

\n

## Solution

\n
\n

#### Approach #1 Brute Force [Accepted]

\n

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

\n\n

Complexity Analysis

\n
\n
• Time complexity : . The complete array(of size ) needs to be scanned for all the elements of in\n the worst case.
• \n
• Space complexity : . array of size is used, where is the length of array.
• \n
\n
\n

#### Approach #2 Better Brute Force [Accepted]

\n

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

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . The whole array, of length needs to be scanned for all the elements of in the worst case.

\n
• \n
• \n

Space complexity : . array of size is used. A hashmap of size is used, where refers to the\n length of the array.

\n
• \n
\n
\n

#### Approach #3 Using Stack [Accepted]

\n

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() and a hashmap(). is used to store the result for every posssible number in in\nthe form of . Now, we look at how to make entries in .

\n

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

\n

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

\n

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 array. Thus, at the end of the iteration over , we pop the remaining\nelements from the and put their entries in with a as their corresponding results.

\n

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

\n

The following animation makes the method clear:

\n

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

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . The entire array(of size ) is scanned only once. The stack\'s elements are popped\n only once. The array is also scanned only once.

\n
• \n
• \n

Space complexity : . and of size is used. array of size is used, where refers to the\n length of the array and refers to the length of the array.

\n
• \n
\n
\n

Analysis written by: @vinod23

\n
'