Code Destine

Problem Statement

You are given two arrays (without duplicates) A and B, where A elements are a subset of array B. Write a program to find the next greater element for each element of array A in the corresponding places of array B.

The next greater element of an element x in array A is the first greater element to its right in array B. If it does not exist, then return -1 for this element.

Example 

Input :- A = [4, 1, 2], B = [1, 3, 4, 2]
Output :- [-1, 3, -1]

Input :- A = [2, 4], B = [1, 2, 3, 4]
Output :- [3, -1]

Solution

The Stack object is used to find out the next greater element for each element of array B and the result is stored in HashMap object with an element of array B as key and next greater element as value. Now each element of array A is searched in HashMap object if the element is present in HashMap, then its value is returned and if it is not present, then -1 is returned.

Program

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class Main {

	public static void main(String[] args) {		
		Main main = new Main();
		int[] result = main.nextGreaterElement(new int[] {2, 4}, new int[] {1, 2, 3, 4});
		for(int i : result) {
			System.out.print(i + ", ");
		}										
	}  
	
	/* Solution */    
	public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        
        Map<Integer, Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
        
        for(int i=0; i<nums2.length; i++){            
            while(stack.size() > 0 && stack.peek() < nums2[i]){
                map.put(stack.pop(), nums2[i]);
            }
            stack.push(nums2[i]);            
        }
        
        for(int i=0; i<nums1.length; i++){  
            if(map.containsKey(nums1[i])){
                nums1[i] = map.get(nums1[i]);   
            }else {
                nums1[i] = -1;
            }                     
        }        
        return nums1;
    }
}

Result

[3, -1]

Similar Post

1. Implement Stack using Queues
2. Implement Queue using Stacks
3. Design Stack using Linked List

If you liked it, please share your thoughts in a comments section and share it with others too.