What is the brute force approach and complexity for Next Smaller Element?

For each element, walk right until a strictly smaller value with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Next Smaller Element?

Scan right to left; pop candidates ≥ current, top is the answer, push current with optimal time complexity O(N) and space complexity O(N).

How do you identify the pattern for Next Smaller Element?

Look for key signals in the prompt: "first element to its right" indicates Nearest-to-the-right question → monotonic stack, not a sort or a range minimum.; "strictly smaller" indicates We keep smaller candidates → increasing stack. Equal values are not answers, so they get popped too (`>=`).; "-1 if none" indicates An empty stack after popping means nothing smaller exists..

Next Smaller Element

Medium·GeeksforGeeks Pro OnlyBasic Reinforcement

GeeksforGeeks

Problem Statement

You are given an integer array arr. For every element, find its next smaller element: the first element to its right that is strictly smaller than it.

If no element to the right is smaller, the answer for that position is -1.

Write nextSmallerEle(arr) that returns these answers as an array of the same length.

Input

An integer array arr of length n.

Output

An array ans of length n, where ans[i] is the first value to the right of arr[i] that is smaller than arr[i], or -1.

Example 1

Input: arr = [4, 8, 5, 2, 25]

Output: [2, 5, 2, -1, -1]

For 4, the values to the right are 8, 5, 2, 25; the first one below 4 is 2. For 8 it is 5. For 5 it is 2. Nothing to the right of 2 is smaller, and 25 is last.

Example 2

Input: arr = [13, 7, 6, 12]

Output: [7, 6, -1, -1]

13 → 7, 7 → 6. Nothing after 6 is smaller. 12 is last.

Example 3

Input: arr = [4, 4, 4]

Output: [-1, -1, -1]

An equal value is not smaller, so nobody has an answer.

Constraints

• 1 ≤ arr.length ≤ 10^5
• 1 ≤ arr[i] ≤ 10^5

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“first element to its right”

→ Nearest-to-the-right question → monotonic stack, not a sort or a range minimum.

“strictly smaller”

→ We keep smaller candidates → increasing stack. Equal values are not answers, so they get popped too (`>=`).

“-1 if none”

→ An empty stack after popping means nothing smaller exists.

Approach Complexity Ladder

Brute Force — scan right for each elementO(N²)O(1)

For each element, walk right until a strictly smaller value

Optimal — right-to-left stack of candidatesO(N)O(N)

Scan right to left; pop candidates ≥ current, top is the answer, push current

Brute Force Intuition

For every i, look at i + 1, i + 2, … and stop at the first value that is < arr[i]. If you reach the end, the answer is -1.

Recognition rule for this sub-pattern:

Need the first smaller value. Keep an increasing stack; greedy "remove bigger digits before me" problems also live here.

Remember this · Monotonic Stack

Trigger

Next/previous greater or smaller element, spans, histogram areas, "for each element, how far does it dominate?"

Think

When a new element arrives, which older elements can never be the answer again?

Key question

Is my stack increasing or decreasing, and what do I record when I pop?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Monotonic Stack translate into production architectures and low-level memory mechanics.

LLD Architecture

Undo / Redo Framework (Command Pattern)

State snapshot management and history stack unwinding.

Explore Track

C++ Internals

Move Semantics & Rvalue References

Eliminating deep copies when pushing and popping complex objects on stacks.

Explore Track

Final Prices With a Special Discount in a Shop Remove K Digits