Cracking The Coding Interview Together – Problem 3.5: Sort Stack

In this edition of Cracking The Coding Interview — Together, we explore a constraint-heavy puzzle. We need to sort a stack using only one additional stack. No arrays, no heaps, no cheating. It’s a classic test of how you manage data flow when your hands are tied.

Imagine you’re an engineer working on a legacy system or a memory-constrained embedded device. You don’t have the luxury of an ArrayList. You don’t have a Heap. You have two stacks and a dream. Let’s get into it.

As always, we’ll follow the same structure that you would use in a real interview.

1. Understand the problem statement together
2. Ask any questions, that you would like to ask the interviewer
3. I would urge you to take your time here and try to come up with your own solution before going forward
4. Think how you would go about solving the problem(you would be talking out loud in front of the actual interviewer)
5. Write code and understand how it works and explain it to your interviewer

Problem statement

Sort Stack: 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). The stack supports the followingoperations: push, pop, peek, and isEmpty.

The Inputs and Outputs:

• Original Stack (Input): [5, 10, 1, 8, 2] (Top is 2)
• Sorted Stack (Target): [10, 8, 5, 2, 1] (Top is 1)

At first glance, you might think: "I'll just find the minimum, put it aside, then find the next minimum..." But wait. How do you "put it aside" without another data structure? That’s where the beauty of this puzzle lies.

Analyse the problem statement together

Before we touch the keyboard, we have to look at our tools. A Stack is a LIFO (Last-In, First-Out) structure. It’s like a vertical tube; you can only see and touch the item at the very top.

In a standard sorting algorithm like QuickSort or MergeSort, we rely on "random access"—the ability to look at any index at any time. Stacks strip that away. We are essentially "blind" to everything except the top element.

The Constraint Check:

1. One additional stack only: We have stack_S (input) and stack_R (temporary).
2. No Arrays/Lists: If I see you converting this to an ArrayList, the interview is over.
3. LIFO operations only: push, pop, peek.

The Mental Model: Think of this like a game of Hanoi Towers mixed with a deck of cards. To get a specific card to the bottom of a pile, you have to move everything on top of it somewhere else first.

Questions for the interviewer

As always, we think like engineers. Before solving, we clarify.

1. Duplicates? "How should we handle duplicate values?" (Usually, they just sit next to each other, but it's good to ask).
2. Nulls/Empty? "Can the stack contain nulls?" (In Java, Stack<Integer> usually deals with primitives or non-null wrappers, but clarify edge cases).
3. Stability? "Does the sort need to be stable?" (For primitives, stability doesn't matter, but for objects, it might).

Assuming the interviewer says: "Standard integers, duplicates allowed, no nulls," we move to the logic.

Think about the Solution

The "Sorted Buffer" Strategy

If we want the smallest items on top of the original stack when we're finished, what does our temporary stack need to look like during the process?

When we move elements from our temporary stack (stack_R) back to the original stack (stack_S), the order reverses. Therefore:

• To have Smallest on Top in S...
• We need Largest on Top in R (Descending order).

The Algorithm: The "Shift and Drop"

We will pull an element from the original stack and try to place it in the temporary stack. But we must keep the temporary stack sorted at all times.

1. Pop the top element from stack_S. Let’s call this tmp.
2. Look at the top of stack_R.
3. If stack_R is empty OR tmp is greater than or equal to the top of stack_R, we can safely push tmp onto stack_R.
4. The Conflict: If tmp is smaller than the top of stack_R, we have a problem. We can’t just drop it on top, or we break our sorted order.
5. The Fix: We pop elements from stack_R and push them back into stack_S until we find the right spot for tmp. Then, we push tmp into stack_R.

Why this works:

By pushing the "blocking" elements back into the original stack, we aren't losing them. We are just putting them back into the "to-be-processed" pile. Eventually, they will come back around and find their correct home in the sorted buffer.

A Step-by-Step Walkthrough (The Dry Run)

Let's trace this with numbers. This is what you should do on a whiteboard.

Initial State: S: [5, 10, 1, 8, 2] (Top is 2) R: [] (Empty)

Step 1: Pop 2 from S. tmp = 2. R is empty, so push 2.

S: [5, 10, 1, 8], R: [2]

Step 2: Pop 8 from S. tmp = 8. 8 > 2? Yes. Push 8 to R.

S: [5, 10, 1], R: [2, 8]

Step 3: Pop 1 from S. tmp = 1.

Is tmp (1) < R.peek() (8)? Yes. Pop 8 from R, push to S.

Is tmp (1) < R.peek() (2)? Yes. Pop 2 from R, push to S.

Now R is empty. Push tmp (1) to R. S: [5, 10, 8, 2], R: [1]

Step 4: Now we repeat. Eventually, R will hold all elements in descending order: [1, 2, 5, 8, 10].

Step 5: Pop everything from R back to S.

Final S: [10, 8, 5, 2, 1] (Smallest is 1, at the top!)

Write code and explain

Now let’s translate this idea into code.

Java code

import java.util.Stack;

public class StackSorter {
    /**
     * Sorts a stack in place (using one auxiliary stack)
     * so that the smallest elements are on top.
     */
    public static void sort(Stack<Integer> s) {
        // This will be our sorted buffer.
        // It will be kept in DESCENDING order (largest on top).
        Stack<Integer> r = new Stack<Integer>();
        
        while (!s.isEmpty()) {
            /* * Step 1: Remove the top element from the original stack 
             */
            int tmp = s.pop();
            
            /* * Step 2: While the temporary stack has elements that are 
             * larger than our current element, we must move them back
             * to the original stack to find the correct insertion point.
             */
            while (!r.isEmpty() && r.peek() > tmp) {
                s.push(r.pop());
            }
            
            /* * Step 3: Insert the element into the correct spot in r 
             */
            r.push(tmp);
        }
        
        /* * Step 4: After s is empty, r is sorted with the largest on top.
         * To get the smallest on top of s, we simply move them all back.
         */
        while (!r.isEmpty()) {
            s.push(r.pop());
        }
    }
}

Explain the Code in Plain English

• Two Stacks: We use stackNewest as our "inbox" and stackOldest as our "outbox."
• shiftStacks(): This is the heart of the class. It only moves data when necessary. If our "outbox" is empty, we flip the "inbox" into it. This puts the oldest elements at the top, ready to be served.
• Efficiency: We don't move elements back to stackNewest. They stay in stackOldest until they are popped. This is "lazy evaluation" in practice.

Time & Space Complexity

This is where the interview gets serious. You need to explain why this isn't the most efficient sort in the world, but why it's the best we can do under these rules.

Time Complexity: O(N^2)

This algorithm is essentially a variation of Insertion Sort.

• In the Best Case (the stack is already sorted in descending order), we just move each element once. That would be O(N).
• In the Worst Case (the stack is already sorted in the order we want—ascending), for every element we pull from s, we have to move almost every element from r back into s, then move them all back to r again.
• The total number of operations follows the sum of integers: 1 + 2 + 3 + ... + N, which mathematically is N(N+1)/2. In Big O notation, we drop the constants and lower terms, leaving us with O(N^2).

Space Complexity: O(N)

We use exactly one additional stack that grows to size $N$. While we use a tmp variable, it only stores one integer at a time ($O(1)$), so the total space is dominated by the second stack.

Refining the Engineer's Perspective: Can we do better?

In a real interview, once you finish the O(N^2) solution, the interviewer might ask: "Can you make this O(N log N)?"

The answer is Yes—but not with these exact constraints.

If you were allowed to use multiple additional stacks, you could implement a Merge Sort or Quick Sort logic.

• Merge Sort with Stacks: You could recursively split the stack into two, sort them, and then merge the two sorted stacks back together.
• Merging two sorted stacks into one sorted stack is an O(N) operation.
• Doing this recursively gives you the classic O(N log N) time.

However, since we are limited to one additional stack, the Insertion Sort approach is the most efficient path.

Why This Problem Matters

You might think, "When am I ever going to be limited to just two stacks?"

The truth is, you probably won't be. But this problem isn't about stacks. It's about In-Place Processing and Data Integrity.

1. State Management: You have to keep track of two different "states" (a random pile and a sorted pile) and move data between them without losing a single integer.
2. Constraint Satisfaction: It forces you to stop reaching for the "easy" tools (like Collections.sort()) and understand how data actually moves in memory.
3. Buffer Logic: This "shuffling" between two containers is the foundation of many low-level data processing tasks, including how some database redo-logs and undo-logs manage transactions.

Final Thoughts

This problem is a "small" one, but it carries a "big" lesson.

When you’re faced with constraints, your first instinct shouldn't be to complain that you need more tools. Your first instinct should be to ask: "How can I use the nature of this structure to my advantage?"

We used the LIFO nature of the stack to reverse data twice—once to sort it into a buffer, and once to flip it back into the original stack in the correct order. That is engineering—using the rules of the system to achieve the desired outcome.

If you followed along, tried the dry run on paper, and understood the O(N^2) trade-off, you’re not just solving problems. You’re building the intuition of a senior engineer.

I’ll see you in the next one.

Happy Coding.