Author at SyntaxFlow
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!
Sorting a stack means rearranging its elements so that the smallest items are on the top, and the largest items are at the bottom.
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.
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:
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.
Example 1:
[34, 3, 31, 98, 92, 23] (where 23 is the top)[98, 92, 34, 31, 23, 3] (where 3 is the top)top() operation.Example 2:
[5, 1, 4, 2, 3] (where 3 is the top)[5, 4, 3, 2, 1] (where 1 is the top)Example 3 (Already Sorted):
[5, 4, 3, 2, 1] (where 1 is the top)[5, 4, 3, 2, 1] (where 1 is the top)Before writing any code, we must acknowledge the strict constraints:
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.
When we try to sort a stack using only one other stack, we can make a few critical observations:
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.
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."
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.
#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);
}
}
};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.
This is the standard, expected solution for this problem. We will sort the stack using nothing but integer variables and one temporary stack.
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.
tmpStack.input stack is not empty:input and store it in an integer variable tmp.tmpStack is NOT empty AND the top of tmpStack is strictly less than tmp:tmpStack and push it back onto input.tmp onto the tmpStack.input stack is empty, tmpStack contains the elements sorted with the smallest on top.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).Let's trace this carefully. Input Stack: [34, 3, 31] (31 is on top). We want [34, 31, 3] (3 on top).
Let's visualize the "shuffle" step (Steps 1-5 from the dry run).
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 fromtmpStackback toinput. Keep in mind that doing this will reverse the order (putting the largest element on top). To fix this, you would change the condition totmpStack.top() > tmp.
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.
Ensure your code doesn't crash on these tricky inputs:
while(!input.empty()) immediately bypasses the logic and returns an empty tmpStack. Handled perfectly.while loop is bypassed because tmpStack is empty. Handled perfectly.while loop condition tmpStack.top() < tmp will always evaluate to false. Operations drop to O(N) time!tmpStack.top() == tmp, the inner while loop condition is false. The duplicate is pushed neatly on top. Handled perfectly.tmp back into the input stack instead of the tmpStack, causing the algorithm to process the same number forever.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.tmp Variable: Forgetting to store input.top() in a variable before calling input.pop(). The value is lost forever, resulting in bugs.< or > in your inner loop.sortStack and insertSorted). Mentioning this will deeply impress the interviewer.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.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.
O(N^2). This is fundamentally an Insertion Sort adapted for LIFO data structures.< 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: