Nearest Smaller Element

 Problem:-

Given an array, find the nearest smaller element G[i] for every element A[i] in the array such that the element has an index smaller than i.

More formally,

G[i] for an element A[i] is an element A[j] such that 
j is maximum possible AND
j < i AND
A[j] < A[i]

Elements for which no smaller element exist, consider next smaller element as -1.

Input Format

First line contains an integer denoting the number of elements in the array (not necessarily distinct).

Second line contains space separated integers denoting the elements of the array.

Output Format

Print space separated integers denoting the array G.

Constraints

 

1N105

0A[i]106

Sample Input
8
39 27 11 4 24 32 32 1
Sample Output
-1 -1 -1 -1 4 24 24 -1
Time Limit: 2
Memory Limit: 256
Source Limit:

Code:-

#include<stdio.h>
long int stack[100000],top=-1;
int main()
{
long int a[100000],i,n;
    scanf(“%ld”,&n);
    for(i=0;i<n;i++)
     scanf(“%ld”,&a[i]);
    top++;
    stack[top]=n1;
    for(i=n2;i>=0;i–)
    {
        if(a[i]>=a[stack[top]])
        {
            top++;
            stack[top]=i;
        }
        else
        {
            while(top!=-1 && a[i]<a[stack[top]])
            {
                a[stack[top]]=a[i];
                top–;
            }
            top++;
            stack[top]=i;
        }
    }
    while(top!=-1)
    {
        a[stack[top]]=-1;
        top–;
    }
    for(i=0;i<n;i++)
     printf(“%ld “,a[i]);
    return 0;
}



Leave a Reply

Your email address will not be published.