Nearest Smaller Element

Rajnish Tripathi 23:03

 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 N denoting the number of elements in the array (not necessarily distinct).

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

Output Format

Print N space separated integers denoting the array G.

Constraints

 1≤N≤105

0≤A[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]=n-1;
    for(i=n-2;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;
}



Tags: