Flip a Stack's Order Using Pure Recursion
Solve this ProblemTest Case 1:
Test Case 2:
Constraints
- ◆
0 ≤ stack.length ≤ 10 - ◆
stack is given bottom-to-top (index 0 is the bottom, the last index is the top) - ◆
-100 ≤ stack[i] ≤ 100 - ◆
Only push, pop, top/peek, and isEmpty are considered valid stack operations for the intended (recursive) technique — no other explicit data structure or loop may be used to reverse the contents
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Iterative — Explicit Array Reversal
OptimalIf an auxiliary array is allowed, reversing a stack's contents is trivial: read the elements from top to bottom and write them into a new array from front to back (or equivalently, copy in reverse index order). This is asymptotically the fastest correct way to reverse the contents, and it's the approach to reach for whenever the "only stack operations, recursion only" constraint isn't actually required by the situation.
O(n)O(n)1class Solution {
2 public int[] reverseStackRecursive(int[] stack) {
3 int n = stack.length;
4 int[] result = new int[n];
5 for (int i = 0; i < n; i++) {
6 result[i] = stack[n - 1 - i];
7 }
8 return result;
9 }
10}Pure Recursion — No Auxiliary Data Structure (Classic Technique)
BetterPop the top element, recursively reverse everything beneath it, then insert the popped element at the very bottom of the now-reversed remainder (using the same recursive "insert at bottom" technique as a sub-routine). This satisfies the classic constraint of using only stack operations and recursion — no second array, no loop. The catch: inserting at the bottom is itself an O(n) recursive operation, and it's called once per level of the outer recursion (n times total), so the total cost is O(n) × O(n) = O(n²) — genuinely slower than the explicit-array approach. This trade-off (accepting O(n²) time to eliminate any auxiliary data structure) is exactly what makes this problem a classic recursion exercise rather than a genuine optimization.
O(n²)O(n) call-stack space, no explicit auxiliary structure1class Solution {
2 public int[] reverseStackRecursive(int[] stack) {
3 List<Integer> list = new ArrayList<>();
4 for (int x : stack) list.add(x);
5 reverseHelper(list);
6 int[] result = new int[list.size()];
7 for (int i = 0; i < list.size(); i++) result[i] = list.get(i);
8 return result;
9 }
10
11 private void reverseHelper(List<Integer> s) {
12 if (s.isEmpty()) return;
13 int top = s.remove(s.size() - 1);
14 reverseHelper(s);
15 insertBottomHelper(s, top);
16 }
17
18 private void insertBottomHelper(List<Integer> s, int val) {
19 if (s.isEmpty()) {
20 s.add(val);
21 return;
22 }
23 int top = s.remove(s.size() - 1);
24 insertBottomHelper(s, val);
25 s.add(top);
26 }
27}