ronith
6/16/2018 - 5:52 AM

Find the nearest smaller numbers on left side in an array

Given an array of integers, find the nearest smaller number for every element such that the smaller element is on left side.

Examples:

Input: arr[] = {1, 6, 4, 10, 2, 5} Output: {_, 1, 1, 4, 1, 2} First element ('1') has no element on left side. For 6, there is only one smaller element on left side '1'. For 10, there are three smaller elements on left side (1, 6 and 4), nearest among the three elements is 4.

Input: arr[] = {1, 3, 0, 2, 5} Output: {_, 1, _, 0, 2}

Stack based algorithm:

Let input sequence be 'arr[]' and size of array be 'n'

  1. Create a new empty stack S

  2. For every element 'arr[i]' in the input sequence 'arr[]', where 'i' goes from 0 to n-1. a) while S is nonempty and the top element of S is greater than or equal to 'arr[i]': pop S

    b) if S is empty: 'arr[i]' has no preceding smaller value c) else: the nearest smaller value to 'arr[i]' is the top element of S

    d) push 'arr[i]' onto S

Find the nearest smaller numbers on left side in an array.cpp
content_copyfile_download
// https://www.geeksforgeeks.org/find-the-nearest-smaller-numbers-on-left-side-in-an-array/
#include <iostream>
#include <stack>
using namespace std;

int func (int a[], int n){
    stack <int> s;

    for (int i=0;i<n;i++){
        while (!s.empty() && s.top() >= a[i])
            s.pop();
        if (s.empty())
            cout << "_ ";
        else
            cout << s.top() << " ";
        s.push(a[i]);
    }
}

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

    int m=a[0];
    func(a,n);
}