Nearest Smaller Values

Given an array of n integers, find for each array position the nearest position to its left having a smaller value.

Example:

Input:  n = 8, arr = {2, 5, 1, 4, 8, 3, 2, 5}
Output: 0 1 0 3 4 3 3 7 

Approach

C++

#include <bits/stdc++.h>
using namespace std;

vector<int> nearestSmallerValues(int n, vector<int> &arr)
{

    stack<int> st;

    vector<int> res;
    for (int i = 0; i < n; i++)
    {
        while (st.size() && arr[st.top()] >= arr[i])
            st.pop();
        if (st.size() > 0)
            res.push_back(st.top() + 1);
        else
            res.push_back(0);

        st.push(i);
    }
    return res;
}

int main()
{

    int n = 8;

    vector<int> arr = {2, 5, 1, 4, 8, 3, 2, 5};

    vector<int> res = nearestSmallerValues(n, arr);

    for (int i = 0; i < res.size(); i++)
        cout << res[i] << " ";

    return 0;
}