Sort a Stack | Brute Force & Optimal Solution Explained

While you won't find this explicitly numbered on LeetCode, it is a legendary problem (famously featured in Cracking the Coding Interview as Problem 3.5) and appears constantly in interviews at top tech companies.

In this comprehensive guide, we will break down the problem, explore a brute-force approach, dive deep into the optimal iterative solution using an auxiliary stack in C++, and cover the tricky edge cases interviewers will ask you about.

Let's dive in!

Introduction

What Does it Mean to Sort a Stack?

Sorting a stack means rearranging its elements so that the smallest items are on the top, and the largest items are at the bottom.

Why is this a Common Interview Question?

Normally, sorting data is straightforward—you just use a built-in sort function. But interviewers ask this question to enforce artificial constraints. They want to see if you can manipulate data when you are strictly limited to the Last-In, First-Out (LIFO) behavior of a stack. It tests your logical reasoning, memory management, and ability to track moving variables.

Real-World Applications

While you will rarely sort a stack in production code (you would use a Priority Queue or sort a Vector instead), the mental gymnastics required for this problem translate directly into:

• Embedded Systems: Managing limited memory buffers where only sequential access is allowed.
• Turing Machine Emulation: Understanding how to compute complex states with severely restricted operations.
• Algorithmic Problem Solving: Building the foundation for advanced algorithms like topological sorting or recursive backtracking.

Problem Statement

The Problem: Write a program to sort a stack such that the smallest items are on the top. You can use an additional temporary stack, but you may not copy the elements into any other data structure (such as an array, vector, or queue). The stack supports the following operations: push, pop, top, and empty.

Examples

Example 1:

• Input Stack: [34, 3, 31, 98, 92, 23] (where 23 is the top)
• Output Stack: [98, 92, 34, 31, 23, 3] (where 3 is the top)
• Explanation: The stack is rearranged so the smallest element (3) is easily accessible via the top() operation.

Example 2:

• Input Stack: [5, 1, 4, 2, 3] (where 3 is the top)
• Output Stack: [5, 4, 3, 2, 1] (where 1 is the top)

Example 3 (Already Sorted):

• Input Stack: [5, 4, 3, 2, 1] (where 1 is the top)
• Output Stack: [5, 4, 3, 2, 1] (where 1 is the top)

Constraints

Before writing any code, we must acknowledge the strict constraints:

• You may use exactly one additional stack.
• You cannot use arrays, vectors, priority queues, or linked lists to hold the data.
• The data contains integers (can be positive, negative, or duplicates).
• Stack size is typically up to 1000 elements.

Why these constraints matter: If you could use an array, you would simply pop all elements into the array, run a built-in O(N log N) sort, and push them back. The "one temporary stack" rule forces you to find an in-place-like O(N^2) algorithm.

Observations

When we try to sort a stack using only one other stack, we can make a few critical observations:

1. The Destination: The temporary stack can double as our final sorted stack.
2. The Shuffle: If we hold an element from the input stack in a temporary integer variable, we can compare it to the top of our temporary stack.
3. Making Room: If the element we are holding is larger than the top of our temporary stack (and we want smallest on top eventually), we must move elements from the temporary stack back to the input stack until we find the correct spot for our held element.

Key Insight: The input stack acts as a buffer. We can temporarily dump elements back into it to maintain the sorted order of our auxiliary stack.

Approach 1: Brute Force (The "Rule Breaker" Educational Approach)

If you are stuck in an interview, it is always better to provide a working solution that breaks constraints than to provide no solution at all. Be sure to explicitly tell the interviewer: "I know this violates the single-stack constraint, but I want to establish a baseline before optimizing."

Intuition

Pop every element out of the stack and place it into a standard Array/Vector. Sort the Array using the language's built-in optimized sorting algorithm. Finally, push the elements back into the stack.

Algorithm

1. Create a dynamic array (Vector in C++).
2. While the input stack is not empty, pop the top element and append it to the array.
3. Sort the array in descending order (so the smallest elements are pushed last and end up on top).
4. Iterate through the array and push everything back into the input stack.

C++ Implementation

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    void sortStackBruteForce(stack<int>& input) {
        vector<int> tempArray;
        
        // Step 1: Empty stack into array
        while (!input.empty()) {
            tempArray.push_back(input.top());
            input.pop();
        }
        
        // Step 2: Sort array descending
        // We want largest at the bottom, so we push them first
        sort(tempArray.begin(), tempArray.end(), greater<int>());
        
        // Step 3: Push back to stack
        for (int num : tempArray) {
            input.push(num);
        }
    }
};

Complexity Analysis

Verdict: Ironically, this brute force method is computationally faster than the expected optimal solution. However, it completely fails the interview constraint (no arrays). Let's look at the real solution.

Approach 2: Optimal Auxiliary Stack Solution

This is the standard, expected solution for this problem. We will sort the stack using nothing but integer variables and one temporary stack.

Intuition

Think of it like sorting a deck of cards into a new pile. You draw a card (let's say a 5). The new pile is empty, so you place the 5 down. You draw another card (an 8). The top of the new pile is a 5. Because 8 is bigger than 5, you have to move the 5 out of the way. You put the 5 back into the original deck, place the 8 down in the new pile, and then draw the 5 again and put it on top of the 8.

Algorithm

1. Create a temporary stack called tmpStack.
2. While the input stack is not empty:
   • Pop the top element from input and store it in an integer variable tmp.
   • While tmpStack is NOT empty AND the top of tmpStack is strictly less than tmp:
     • Pop the top of tmpStack and push it back onto input.
   • Push tmp onto the tmpStack.
3. Once the input stack is empty, tmpStack contains the elements sorted with the smallest on top.
4. (Optional) If the interviewer wants the original stack modified in-place, pop everything from tmpStack back to input (wait, if we do that, the largest will be on top. To keep the smallest on top, tmpStack is already correct, so we just return it or re-reverse it if needed).

Dry Run

Let's trace this carefully. Input Stack: [34, 3, 31] (31 is on top). We want [34, 31, 3] (3 on top).

Visual Illustration

Let's visualize the "shuffle" step (Steps 1-5 from the dry run).

C++ Implementation

Here is the clean, optimal solution using a single auxiliary stack.

#include <iostream>
#include <stack>

using namespace std;

class Solution {
public:
    // Function to sort a stack using another temporary stack
    stack<int> sortStack(stack<int>& input) {
        stack<int> tmpStack;  // Temporary stack to hold sorted elements
        
        // Continue until the input stack becomes empty
        while (!input.empty()) {
            // Step 1: Pop the top element from the input stack
            int tmp = input.top();
            input.pop();
            
            // Step 2: Move elements from tmpStack back to input
            // while they are smaller than the current element (tmp)
            // This ensures tmpStack remains sorted in descending order
            while (!tmpStack.empty() && tmpStack.top() < tmp) {
                input.push(tmpStack.top());  // Move smaller element back
                tmpStack.pop();              // Remove it from tmpStack
            }
            
            // Step 3: Push the current element into tmpStack
            // It will be placed in the correct position relative to others
            tmpStack.push(tmp);
        }
        
        // At the end, tmpStack contains elements in sorted order (descending)
        return tmpStack;  // Return the sorted stack
    }
};

Best Practice Note: If the function signature requires you to sort the stack in-place (i.e., void sortStack(stack<int>& input)), simply run the algorithm above, then pop everything from tmpStack back to input. Keep in mind that doing this will reverse the order (putting the largest element on top). To fix this, you would change the condition to tmpStack.top() > tmp.

Complexity Analysis

Comparison Table

Notice the irony here: to satisfy the constraint of the stack data structure, we are forced to write a slower algorithm. This highlights that data structure constraints heavily dictate algorithmic efficiency.

Edge Cases

Ensure your code doesn't crash on these tricky inputs:

• Empty Stack: The outer while(!input.empty()) immediately bypasses the logic and returns an empty tmpStack. Handled perfectly.
• Single Element Stack: Outer loop runs once, inner while loop is bypassed because tmpStack is empty. Handled perfectly.
• Already Sorted Stack: The inner while loop condition tmpStack.top() < tmp will always evaluate to false. Operations drop to O(N) time!
• Duplicates in Stack: If tmpStack.top() == tmp, the inner while loop condition is false. The duplicate is pushed neatly on top. Handled perfectly.

Common Mistakes

1. Infinite Loops: Accidentally pushing tmp back into the input stack instead of the tmpStack, causing the algorithm to process the same number forever.
2. Wrong Inequality Sign: Using tmpStack.top() > tmp when you wanted the smallest elements on top. Always dry-run two numbers mentally (e.g., 3 and 5) to double-check your sign.
3. Losing the tmp Variable: Forgetting to store input.top() in a variable before calling input.pop(). The value is lost forever, resulting in bugs.

Interview Tips

• Clarify the "Top": Before coding, ask the interviewer, "Do you want the smallest element on the top or the bottom?" This determines whether you use < or > in your inner loop.
• The Recursive Variation: Interviewers might ask, "Can you do this without ANY auxiliary stack?" The answer is Yes, using Recursion. Recursion uses the computer's Call Stack as the temporary stack! (You write two recursive functions: sortStack and insertSorted). Mentioning this will deeply impress the interviewer.
• Embrace the O(N^2): Don't apologize for the O(N^2) time complexity. Explain confidently that under the constraint of using only stack operations, O(N^2) is the mathematically optimal bound.

FAQs

1. Why is the Optimal Stack solution slower than the Brute Force Array solution? Because a stack only allows access to one end (the top). In an array, you have random access to any element, enabling efficient algorithms like QuickSort or MergeSort. Stacks force us to essentially perform an Insertion Sort.

2. Can we achieve O(N log N) using only stacks? Technically, if you are allowed two or more auxiliary stacks, you can implement a form of Merge Sort on stacks to achieve O(N log N). However, with strictly one auxiliary stack, O(N^2) is the limit.

3. What if there are duplicate numbers? Our code handles duplicates natively. The condition tmpStack.top() < tmp ensures that equal numbers simply stack on top of each other without triggering the shuffle step.

4. How does recursion solve this? Recursion stores the popped variables in the function's local execution frame. As the recursion unwinds, it inserts the elements back in sorted order. It still takes O(N^2) time and O(N) space (via the call stack).

5. Why did you use std::stack instead of a custom class? In C++ interviews, using the Standard Template Library (STL) std::stack is heavily preferred to save time, unless the interviewer specifically asks you to build a stack from scratch.

6. Is this problem asked at FAANG? Yes, though usually as a warm-up or part of a multi-stage problem (e.g., "Sort this data stream but you are only allowed to use LIFO buffers"). Amazon and Microsoft frequently test basic stack manipulations.

7. Does the initial state of the input stack matter? Yes, for performance. If the input stack is already reverse-sorted (which means it perfectly feeds into our tmpStack in sorted order), the time complexity drops to O(N).

8. Can I solve this using a Queue? The problem strictly forbids queues. If allowed, using a queue doesn't significantly change the time complexity, but it changes the logic to a BFS-style rotation.

9. What happens if the stack holds strings instead of integers? The exact same logic applies! C++ handles string comparisons lexicographically, so tmpStack.top() < tmp will sort strings alphabetically.

10. Why is this considered an "easy/medium" problem? The code itself is quite short (barely 15 lines), but conceptually tracing the movement of variables back and forth across two stacks can be highly confusing under interview pressure.

Key Takeaways

• Sorting a stack tests your ability to work within strict constraints.
• An auxiliary stack acts as your sorted destination. By intelligently moving elements back to the input buffer, you can "insert" items into the middle of your sorted stack.
• The time complexity is O(N^2). This is fundamentally an Insertion Sort adapted for LIFO data structures.
• Pay close attention to inequalities. The difference between < and > dictates whether the smallest or largest element ends up on top.

Take some time to mentally trace the "shuffling" of elements back and forth. Grab a piece of paper, draw two stacks, and run the algorithm by hand. Once you visualize the mechanics, this classic interview problem becomes second nature!

video link:

code link:

https://www.naukri.com/code360/problems/sort-a-stack_985275