Next Greater Element

Concepts Used:

Stacks.

Difficulty Level:

Medium.

Problem Statement :

Arnab is standing in a queue and he is irritated by the tall man standing after him, as he is obstructing his view.

Now Arnab wants to know the height of that tall person in front of him.

Arnab thinks to find a general solution, so for every person, he wants to find the height of the person who is closest to that person and obstructing the view.

For the last person or if there is no one taller he print 0.

Help Arnab solve the problem.

See original problem statement here

Test Case:

Input:
1
5
1 2 3 4 5

Output:
2 3 4 5 0

Explanation:
The second person blocks the view of the 1st person ,so it is 2 and similarly for 2nd person 3rd person blocks the view. 
So the answer is 2 3 4 5 0.

Solving Approach:

  1. This is a simple and basic problem of stack wherein you have to pop elements from the stack until you find a greater element at top.

  2. Start traversing from the last element.

Solutions:

#include 
     int main()
    {  

    int t;
    scanf("%d",&t);
    while(t--)
    {
    int n;
    scanf("%d",&n);
    int a[n];
    for(int i=0;i= 0; i--)  
    { 
        while (top>=0 && s[top] <= a[i]) 
            top--; 
        if (top==-1)  
            ans[i] = 0;          
        else 
            ans[i] = s[top];         

        s[++top]=a[i]; 
    } 

    for(int i=0;i



						 
#include 
     using namespace std;
     int main()
    {  

    int t;
    cin>>t;
    while(t--)
    {
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i>a[i];

    stack s; 

    int ans[n]; 

    for (int i = n - 1; i >= 0; i--)  
    { 
        while (!s.empty() && s.top() <= a[i]) 
            s.pop(); 
        if (s.empty())  
            ans[i] = 0;          
        else 
            ans[i] = s.top();         

        s.push(a[i]); 
    } 

    for(int i=0;i

						 

import java.util.Stack;
class Prepbytes {

    // This function will find the next greater element for each 
    // element
    public static int[] nextGreaterElement(int arr[], int n)
    {
          Stack<Integer> st = new Stack<>();
	    int ans[] = new int[n];
	    
	    // Iterate over the given array
	    for(int i = n - 1; i>= 0; i--){
	        
	        // While stack is not empty and the current
	        // element is greater than the top of the
	        // stack, keeping removing the top of the stack
	        while(!st.isEmpty() && arr[i] >= st.peek()){
	            st.pop();
	        }
	        
	        // If the stack is empty, then it mean there is no next greater
	        // element for this element
	        if(st.isEmpty()){
	            ans[i] = -1;
	        } 
	        // Otherwise, the top of the stack is the next greater
	        // element for this element
	        else {
	            ans[i] = st.peek();
	        }
	        
	        // Push the current element to the stack
	        st.push(arr[i]);
	    }
	    return ans;

    }
    
    public static void main(String[] args) {
        int arr[] = new int[]{1, 4, 2, 17, 9, 12};
        int ans[] = nextGreaterElement(arr, arr.length);
        for(int e : ans){
            System.out.print(e+" ");
        }
    }
}
# your code goes herefor _ in range(int(input())):
    n = int(input())
    a = list(map(int,input().split()))
    s = []
    ans = [0 for i in range(n)]
    for i in range(n-1, -1, -1):
        while s and s[-1] <= a[i]:
            s.pop()
        if not s:
            ans[i] = 0
        else:
            ans[i] = s[-1]
        s.append(a[i])
    print(*ans)

[forminator_quiz id="1987"]

This article tried to discuss Stacks. Hope this blog helps you understand and solve the problem. To practice more problems on Stacks you can check out MYCODE | Competitive Programming.

Leave a Reply

Your email address will not be published. Required fields are marked *