Log inSign up
mediumInterviewBitNot Started

Next Smaller Element

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Stack
Solve on InterviewBit
Lesson

Problem Statement

Given an array of integers A, find the nearest smaller element G[i] for every element A[i] such that the element has an index smaller than i (j < i and A[j] < A[i]).

If no such element exists, then consider the answer as -1.

Example 1 · Standard Array:

Input: A = [4, 5, 2, 10, 8]
Output: [-1, 4, -1, 2, 2]
Explanation: For 4: no element on left -> -1. For 5: 4 < 5 -> 4. For 2: no smaller on left -> -1. For 10: nearest smaller is 2. For 8: nearest smaller is 2.

Example 2 · Strictly Increasing:

Input: A = [3, 2, 1]
Output: [-1, -1, -1]
Explanation: Every element is smaller than previous elements, so no smaller element exists on the left.

Constraints:

  • 1 <= A.length <= 105
  • -109 <= A[i] <= 109

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the dual invariant: Monotonic Increasing Stack finds Smaller Elements, Monotonic Decreasing Stack finds Greater Elements.
  • Eliminate useless larger elements in O(1) amortized steps.
  • Form the fundamental building block for Largest Rectangle in Histogram.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Algorithmic Decision Tree:

  • Traverse from left to right (index 0 to N-1).
  • While stack is not empty and stack.top() >= A[i], pop stack.
  • Set ans[i] = stack.empty() ? -1 : stack.top().
  • Push A[i] onto stack.

Connected Patterns:

Next Greater Element ILargest Rectangle in HistogramOnline Stock Span

1. Leftward Linear Scan

Intuition

For each index i, loop backwards from j = i - 1 down to 0 and find the first A[j] < A[i].

Algorithm

  1. Step 1: Initialize result array G of size N with -1.
  2. Step 2: Loop i from 0 to N - 1.
  3. Step 3: Loop j from i - 1 down to 0.
  4. Step 4: If A[j] < A[i], set G[i] = A[j] and break inner loop.
  5. Step 5: Return G.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 std::vector<int> prevSmaller(std::vector<int>& A) {
7 int n = A.size();
8 std::vector<int> G(n, -1);
9 for (int i = 0; i < n; i++) {
10 for (int j = i - 1; j >= 0; j--) {
11 if (A[j] < A[i]) {
12 G[i] = A[j];
13 break;
14 }
15 }
16 }
17 return G;
18 }
19};
20
21int main() {
22 Solution solver;
23 std::vector<int> A = {4, 5, 2, 10, 8};
24 std::vector<int> ans = solver.prevSmaller(A);
25 std::cout << "Output: [";
26 for (size_t i = 0; i < ans.size(); i++) {
27 std::cout << ans[i] << (i + 1 < ans.size() ? ", " : "");
28 }
29 std::cout << "]" << std::endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(N^2) — For each element i, scan leftwards through all j < i until a strictly smaller element is encountered.
  • Space complexity: O(1) — O(1) extra space beyond output array.

Why Brute Force Doesn't Scale:

A strictly decreasing array takes N*(N-1)/2 comparisons.

At N = 100,000, Monotonic Stack executes in <15ms vs TLE (>10s) for brute force.

2. Vector Buffer Search with Pruning

Intuition

Maintain an explicit dynamic buffer list that shrinks whenever a smaller element invalidates larger tail values.

Algorithm

  1. Step 1: Create a buffer array buf.
  2. Step 2: For each element x in A, trim buf from the back while buf.back() >= x.
  3. Step 3: If buf has items, G[i] = buf.back(), else -1.
  4. Step 4: Append x to buf.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 std::vector<int> prevSmaller(std::vector<int>& A) {
7 int n = A.size();
8 std::vector<int> G(n, -1);
9 std::vector<int> buf;
10 for (int i = 0; i < n; i++) {
11 while (!buf.empty() && buf.back() >= A[i]) {
12 buf.pop_back();
13 }
14 if (!buf.empty()) {
15 G[i] = buf.back();
16 }
17 buf.push_back(A[i]);
18 }
19 return G;
20 }
21};
22
23int main() {
24 Solution solver;
25 std::vector<int> A = {4, 5, 2, 10, 8};
26 std::vector<int> ans = solver.prevSmaller(A);
27 std::cout << "Output: [";
28 for (size_t i = 0; i < ans.size(); i++) {
29 std::cout << ans[i] << (i + 1 < ans.size() ? ", " : "");
30 }
31 std::cout << "]" << std::endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(N) — Pruning elements from the tail of a dynamic buffer guarantees amortized O(N) operations.
  • Space complexity: O(N) — O(N) buffer array.

3. Optimal Monotonic Increasing Stack

Intuition

Maintain an explicit monotonic increasing stack. Any element >= A[i] will never be useful for A[i] or any future element to the right of A[i], because A[i] is both smaller and closer.

Algorithm

  1. Step 1: Initialize an empty stack st and answer array G of size N.
  2. Step 2: Loop i from 0 to N - 1.
  3. Step 3: While st is non-empty and st.top() >= A[i], pop st.
  4. Step 4: If st is non-empty, G[i] = st.top(), else G[i] = -1.
  5. Step 5: Push A[i] onto st.
  6. Step 6: Return G.

Monotonic Increasing Stack Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Stack: [4]
Visual state
Values and pointers at this exact step
stack
This stack trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Why this step matters

Stack: [4]

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <stack>
4
5class Solution {
6public:
7 std::vector<int> prevSmaller(std::vector<int>& A) {
8 int n = A.size();
9 std::vector<int> G(n, -1);
10 std::stack<int> st;
11 for (int i = 0; i < n; i++) {
12 while (!st.empty() && st.top() >= A[i]) {
13 st.pop();
14 }
15 if (!st.empty()) {
16 G[i] = st.top();
17 }
18 st.push(A[i]);
19 }
20 return G;
21 }
22};
23
24int main() {
25 Solution solver;
26 std::vector<int> A = {4, 5, 2, 10, 8};
27 std::vector<int> ans = solver.prevSmaller(A);
28 std::cout << "Output: [";
29 for (size_t i = 0; i < ans.size(); i++) {
30 std::cout << ans[i] << (i + 1 < ans.size() ? ", " : "");
31 }
32 std::cout << "]" << std::endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(N) — Each element is pushed once and popped at most once across the single forward pass.
  • Space complexity: O(N) — O(N) stack space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Leftward Linear ScanO(N^2)O(1)Scan left from each index until a smaller element is found.Redundant comparisons on monotonically arranged prefixes.
2.Vector Buffer with PruningO(N)O(N)Maintain an explicit dynamic buffer list and pop back elements.Resizing overhead.
3.Optimal Monotonic Increasing StackOptimalO(N)O(N)Monotonic strictly increasing stack with immediate O(1) top lookup.None (Optimal).

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Using > instead of >= in st.top() >= A[i] (equal elements must be popped for strict inequality).

Pitfall 2:

Scanning right instead of left.

Pitfall 3:

Popping without checking !st.empty().

Crucial Edge Cases to Validate:

  • Strictly increasing array (e.g. `[1, 2, 3, 4]`) — Each element's nearest smaller is its immediate left neighbor [-1, 1, 2, 3].
  • Strictly decreasing array (e.g. `[4, 3, 2, 1]`) — No smaller elements on left; returns [-1, -1, -1, -1].
  • All identical elements (e.g. `[3, 3, 3]`) — Strictly smaller is required; returns [-1, -1, -1].
  • Single element array `[7]` — Returns [-1].

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Articulate the monotonicity principle clearly: 'We maintain an increasing stack from bottom to top'.
  2. Explain the shadowing intuition: current smaller element completely shadows any larger preceding elements for future queries.
  3. Contrast this with Next Greater Element: Greater uses decreasing stack, Smaller uses increasing stack.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why can we safely pop elements from the stack that are greater than or equal to A[i]?

2.What is the monotonicity maintained by the stack in this problem?

Back to DSA Sheet