Question

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.

Summary

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

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 this number.

Solution


Approach #1 Brute Force [Accepted]

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

Java

public class Solution {
    public int[] nextGreaterElement(int[] findNums, int[] nums) {
        int[] res = new int[findNums.length];
        int j;
        for (int i = 0; i < findNums.length; i++) {
            boolean found = false;
            for (j = 0; j < nums.length; j++) {
                if (found && nums[j] > findNums[i]) {
                    res[i] = nums[j];
                    break;
                }
                if (nums[j] == findNums[i]) {
                    found = true;
                }
            }
            if (j == nums.length) {
                res[i] = -1;
            }
        }
        return res;
    }
}

Complexity Analysis

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

Approach #2 Better Brute Force [Accepted]

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

Java

public class Solution {
    public int[] nextGreaterElement(int[] findNums, int[] nums) {
        HashMap < Integer, Integer > hash = new HashMap < > ();
        int[] res = new int[findNums.length];
        int j;
        for (int i = 0; i < nums.length; i++) {
            hash.put(nums[i], i);
        }
        for (int i = 0; i < findNums.length; i++) {
            for (j = hash.get(findNums[i]) + 1; j < nums.length; j++) {

                if (findNums[i] < nums[j]) {
                    res[i] = nums[j];
                    break;
                }
            }
            if (j == nums.length) {
                res[i] = -1;
            }
        }
        return res;
    }
}

Complexity Analysis

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

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


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

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

If we encounter an element such that , we keep on popping all the elements from until we encounter such that . For every element popped out of the stack , we put the popped element along with its next greater number(result) into the hashmap , in the form . Now, it is obvious that the next greater element for all elements , such that is (since this larger element caused all the 's to be popped out). We stop popping the elements at because this can't act as the next greater element for 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 ones for which no next greater element exists in the array. Thus, at the end of the iteration over , we pop the remaining elements from the and put their entries in with a as their corresponding results.

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

The following animation makes the method clear:

Next_Greater_Element_1

Java

public class Solution {
    public int[] nextGreaterElement(int[] findNums, int[] nums) {
        Stack < Integer > stack = new Stack < > ();
        HashMap < Integer, Integer > map = new HashMap < > ();
        int[] res = new int[findNums.length];
        for (int i = 0; i < nums.length; i++) {
            while (!stack.empty() && nums[i] > stack.peek())
                map.put(stack.pop(), nums[i]);
            stack.push(nums[i]);
        }
        while (!stack.empty())
            map.put(stack.pop(), -1);
        for (int i = 0; i < findNums.length; i++) {
            res[i] = map.get(findNums[i]);
        }
        return res;
    }
}

Complexity Analysis

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

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


Analysis written by: @vinod23

Average Rating: 5 (8 votes)

Subscribe

subscribe for articles.

You have already subscribed for articles.

{[{ ac.errorInfo || "Something wrong. Please try again later."}]}

Success!

Send Feedback