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

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}
Expected time complexity is O(n).

// C++ implementation of efficient algorithm to find
// smaller element on left side
#include <iostream>
#include <stack>
using namespace std;
 
// Prints smaller elements on left side of every element
void printPrevSmaller(int arr[], int n)
{
    // Create an empty stack
    stack<int> S;
 
    // Traverse all array elements
    for (int i=0; i<n; i++)
    {
        // Keep removing top element from S while the top
        // element is greater than or equal to arr[i]
        while (!S.empty() && S.top() >= arr[i])
            S.pop();
 
        // If all elements in S were greater than arr[i]
        if (S.empty())
            cout << "_, ";
        else  //Else print the nearest smaller element
            cout << S.top() << ", ";
 
        // Push this element
        S.push(arr[i]);
    }
}
 
/* Driver program to test insertion sort */
int main()
{
    int arr[] = {1, 3, 0, 2, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    printPrevSmaller(arr, n);
    return 0;
}
Output:

_, 1, _, 0, 2,

import java.util.Stack;
 
//Java implementation of efficient algorithm to find 
// smaller element on left side 
class GFG {
 
// Prints smaller elements on left side of every element 
    static void printPrevSmaller(int arr[], int n) {
        // Create an empty stack 
        Stack<Integer> S = new Stack<>();
 
        // Traverse all array elements 
        for (int i = 0; i < n; i++) {
            // Keep removing top element from S while the top 
            // element is greater than or equal to arr[i] 
            while (!S.empty() && S.peek() >= arr[i]) {
                S.pop();
            }
 
            // If all elements in S were greater than arr[i] 
            if (S.empty()) {
                System.out.print("_, ");
            } else //Else print the nearest smaller element 
            {
                System.out.print(S.peek() + ", ");
            }
 
            // Push this element 
            S.push(arr[i]);
        }
    }
 
    /* Driver program to test insertion sort */
    public static void main(String[] args) {
        int arr[] = {1, 3, 0, 2, 5};
        int n = arr.length;
        printPrevSmaller(arr, n);
    }
}
Output:

_, 1, _, 0, 2,


# Python3 implementation of efficient 
# algorithm to find smaller element
# on left side
import math as mt
 
# Prints smaller elements on left 
# side of every element
def printPrevSmaller(arr, n):
 
    # Create an empty stack
    S = list()
 
    # Traverse all array elements
    for i in range(n):
     
        # Keep removing top element from S 
        # while the top element is greater 
        # than or equal to arr[i]
        while (len(S) > 0 and S[-1] >= arr[i]):
            S.pop()
 
        # If all elements in S were greater
        # than arr[i]
        if (len(S) == 0):
            print("_, ", end = "")
        else: # Else print the nearest 
              # smaller element
            print(S[-1], end = ", ")
 
        # Push this element
        S.append(arr[i])
     
# Driver Code
arr = [ 1, 3, 0, 2, 5]
n = len(arr)
printPrevSmaller(arr, n)
 
# This code is contributed by
# Mohit kumar 29
Output:

_, 1, _, 0, 2,