You are given two arrays (without duplicates)
nums1
andnums2
wherenums1
’s elements are subset ofnums2
. Find all the next greater numbers fornums1
's elements in the corresponding places ofnums2
.The Next Greater Number of a number x in
nums1
is the first greater number to its right innums2
. 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
andnums2
are unique.- The length of both
nums1
andnums2
would not exceed 1000.
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.
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
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.
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:
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
subscribe for articles.
You have already subscribed for articles.
{[{ ac.errorInfo || "Something wrong. Please try again later."}]}
Success!