Stack: Nearest smaller numbers on left side in an array

Problem Statement:

Given an array, you need to find the nearest smaller number for every element on its left side.

Example:

Input : [1, 6, 0, 4, 5, 6]
Output : [-1, 1, -1, 0, 4, 5]

Solution 1: Naive Solution

we need to use 2 nested loops.

Outer loop starts from the second element.

Inner loop goes to all elements on the left side of the element picked by the outer loop.

Time Complexity: O(n^2)
Space Complexity: O(1)

Solution 2: Efficient Solution

Take an empty stack.

Iterate over each element in the array from (0 to n-1)

Till the stack is not empty, if the top element of the stack is greater than or equal to arr[i], pop the stack.

This will make sure that we are left with the elements in the stack that are smaller than arr[i].

If the stack is empty, then arr[i] has to previous smaller element. Then return -1

If the stack is not empty, then near smallest element is the top element of the stack.

Push arr[i] onto the stack.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

void solution_1(const vector<int>& arr)
{
    cout << "-1 ";

    for (int i = 1; i < arr.size(); i++) 
    {
        int j;

        for (j = i - 1; j >= 0; j--) 
        {
            if (arr[j] < arr[i]) 
            {
                cout << arr[j] << " ";
                break;
            }
        }

        if (j == -1)
            cout << "-1 ";
    }

    cout<<"\n";
}

void solution_2(vector<int>& arr)
{
    stack<int> s;

    for (int i = 0; i < arr.size(); i++)
    {
        while (!s.empty() && s.top() >= arr[i])
            s.pop();

        if (s.empty())
            cout << "-1 ";
        else
            cout << s.top() << " ";

        s.push(arr[i]);
    }
}

int main()
{
    vector<int> arr = {1, 6, 0, 4, 5, 6}; 
    solution_1(arr);
    solution_2(arr);
    return 0;
}

Output
————-

-1 1 -1 0 4 5 
-1 1 -1 0 4 5