{"post":"

Problem

Find the next smaller element to the left in an array.

Brute Force Approach

By using two nested for loops we can find the next smaller element to left.

TC – O(N2)

Optimal Approach

We can use a stack to reduce the time complexity. We will use the stack to find the smaller element in left.

Traverse the array from the start, if the stack is empty push -1 to ans vector and push the current value to the stack.
If the stack is not empty, check if the stack top is smaller than the current value if yes then push stack top to ans array and the current value to stack.
Else pop the stack until tack top is smaller than the current value, and if the stack is empty push -1 and current value to stack.
There will no need for elements that are popped because they are popped only because they are greater than current element.

#include<bits/stdc++.h>\nusing namespace std;\n\nvoid nextSmallerElementLeft(vector<int> &vec){\n  \tint size = vec.size();\n\t/* O(N^2)\n  \tvector<int> ans;\n  \tfor(int i = 0; i < size; i++){\n      \tint flag = 0;\n    \tfor(int j = 0; j < i; j++){\n    \t\tif(vec[j] < vec[i]){\n            \tans.push_back(vec[j]);\n              \tflag = 1;\n              \tbreak;\n            }\n    \t}\n      \tif(flag == 0) ans.push_back(-1);\n    }\n  \tvec = ans;\n    */\n\n  \tstack <int> s;\n  \tvector<int> ans;\n  \tfor(int i = 0; i < size; i++){\n    \tif(s.empty()){\n          \ts.push(vec[i]);\n        \tans.push_back(-1);\n        } else if(s.top() < vec[i]){\n            ans.push_back(s.top());\n            s.push(vec[i]);\n        }else{\n        \twhile(!s.empty()){\n            \tif(s.top() < vec[i]){\n                  \tans.push_back(s.top());\n            \t\ts.push(vec[i]);\n                  \tbreak;\n                }\n              \ts.pop();\n            }\n          \tif(s.empty()){\n              \ts.push(vec[i]);\n            \tans.push_back(-1);\n            }\n        }\n    }\n  \t//reverse(ans.begin(), ans.end());\n  \tvec = ans;\n}\n\nint main() {\n\tvector<int> vec = {1,3,2,4};\n  \tnextSmallerElementLeft(vec);\n  \tfor(auto num:vec) cout<<num<<\" \";\n    return 0;\n}\n

TC – O(N) // stack push pop is O(1)

SC – O(N)

\n","title":"Next Smaller Element to Left in an array","authorDetails":{"name":"studymite","slug":"admin"},"description":"Discover the methods to find the next smaller element to the left of an array using both brute force and optimal approaches. ","slug":"next-smaller-element-to-left-in-an-array/","articleId":"636a83417bb1ce5072622afa","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}