Push a Value to the Very Bottom of a Stack
Solve this Problemval, insert val at the very bottom of the stack, preserving the relative order of everything already there — using only the standard stack operations (push, pop, top, isEmpty), with no other explicit data structure to hold values in transit.
Recursion turns out to be exactly the tool for this: popping the top element and holding it as a local variable in the current recursive call is functionally identical to pushing it onto an auxiliary stack — except the "stack" being used is the program's own call stack, never declared explicitly anywhere in the code. Recursing all the way down to an empty stack (the base case) is where the new value actually gets pushed; as the recursion unwinds, each call restores its own held-aside value on top, rebuilding the original order above the new bottom.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ stack.length ≤ 12 - ◆
stack is given bottom-to-top (index 0 is the bottom, the last index is the top) - ◆
-100 ≤ stack[i], val ≤ 100 - ◆
Only push, pop, top/peek, and isEmpty are considered valid stack operations — no other data structure may be used to solve this with the intended technique
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Explicit Auxiliary Stack
GoodUse a second, explicit array as a temporary stack. Pop every element off the original stack and push it onto the temporary one (this naturally reverses their order). Push the new value onto the now-empty original stack. Then pop everything off the temporary stack and push it back onto the original — restoring the original relative order, now sitting above the new bottom value. This is straightforward and correct, but it relies on an extra, explicitly-managed data structure to hold values in transit.
O(n)O(n) explicit auxiliary space1class Solution {
2 public int[] insertAtBottom(int[] stack, int val) {
3 int n = stack.length;
4 int[] temp = new int[n];
5 int tempTop = -1;
6 for (int i = n - 1; i >= 0; i--) {
7 temp[++tempTop] = stack[i];
8 }
9 int[] result = new int[n + 1];
10 int resultTop = -1;
11 result[++resultTop] = val;
12 while (tempTop >= 0) {
13 result[++resultTop] = temp[tempTop--];
14 }
15 return result;
16 }
17}Optimal — Pure Recursion, No Auxiliary Data Structure
OptimalPop the top element and set it aside — not into an explicit data structure, but simply as a local variable held on the current recursive call's own stack frame — then recurse on what remains. The base case (an empty stack) is where the new value actually gets pushed. As each recursive call returns, it pushes its own held-aside value back on top, restoring everything in its original order above the newly inserted bottom value. The call stack itself does the job the auxiliary array did in the brute force — no second data structure is ever explicitly declared.
O(n)O(n) call-stack space, no explicit auxiliary structure1class Solution {
2 public int[] insertAtBottom(int[] stack, int val) {
3 List<Integer> list = new ArrayList<>();
4 for (int x : stack) list.add(x);
5 insertHelper(list, val);
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 insertHelper(List<Integer> s, int val) {
12 if (s.isEmpty()) {
13 s.add(val);
14 return;
15 }
16 int top = s.remove(s.size() - 1);
17 insertHelper(s, val);
18 s.add(top);
19 }
20}