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 know data structures in c++ to pop elements from the stack until you find a greater element at top.

  2. Start traversing from the last element.

Solutions:

    #include <stdio.h>
     int main()
    {  

    int t;
    scanf("%d",&t);
    while(t--)
    {
    int n;
    scanf("%d",&n);
    int a[n];
    for(int i=0;i<n;i++)
    scanf("%d",&a[i]);

    int s[n];
    int top=-1;

    int ans[n]; 

    for (int i = n - 1; 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<n;i++)
    printf("%d ",ans[i]);
    printf("\n");

     } 
     return 0;
     }
     #include <bits/stdc++.h>
     using namespace std;
     int main()
    {  

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

    stack<int> 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<n;i++)
    cout<<ans[i]<<" ";
    cout<<endl;

     } 
     return 0;
     }
      import java.io.*; 
      import java.util.*; 
      import java.lang.*; 

      class prepbytes 
      { 
      static void prevGreater(int arr[],  
                        int n) 
    { 
    Stack<Integer> s = new Stack<Integer>(); 
    // s.push(arr[0]);  
    for (int i = n-1; i >=0; i--)  
    { 
        while (s.empty() == false &&  
            s.peek() < arr[i]) 
            s.pop();
        if (s.empty() == true)  
            System.out.print("0 "); 
        else
            System.out.print(s.peek() + " "); 

        s.push(arr[i]); 
    } 

    } 
     public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int t= sc.nextInt();
        while(t-- >0 ){
            int n = sc.nextInt();
            int a[]=new int[n];
            for(int i=0;i<n;i++)
            {
                a[i] = sc.nextInt();
            }
            prevGreater(a,n);
            System.out.print("\n");
    }}}
Previous post Longest Path
Next post Hop Digits

Leave a Reply

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