Delete the Middle Element of a Stack Using Recursion
Solve this ProblemTest Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ stack.length ≤ 11 - ◆
stack is given bottom-to-top (index 0 is the bottom, the last index is the top) - ◆
-100 ≤ stack[i] ≤ 100 - ◆
The 'middle' element, counted 1-indexed from the bottom, is at position ⌈n/2⌉ — for an even-length stack, this is the one closer to the bottom of the two middle elements - ◆
Only push, pop, top/peek, and isEmpty are considered valid stack operations for the intended (recursive) technique — no other explicit data structure or index-based access may be used
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Compute the Index, Rebuild the Array
GoodIf direct indexed access is allowed, this is immediate: compute the 0-indexed position to remove (⌈n/2⌉-1, counting from the bottom), then build a new array copying every element except the one at that position. Simple and linear, but it reaches past the "only stack operations" constraint by indexing directly into the middle of the structure — something a real stack ADT (LIFO access only) doesn't actually support.
O(n)O(n)1class Solution {
2 public int[] deleteMiddleRecursive(int[] stack) {
3 int n = stack.length;
4 int removeIdx = (int) Math.ceil(n / 2.0) - 1;
5 int[] result = new int[n - 1];
6 int idx = 0;
7 for (int i = 0; i < n; i++) {
8 if (i != removeIdx) result[idx++] = stack[i];
9 }
10 return result;
11 }
12}Optimal — Pure Recursion, No Auxiliary Data Structure
OptimalTrack how many elements have been popped so far as the recursion descends. Pop the top, hold it in the current call's local variable, and recurse — until the count of pops reaches the target depth (⌊n/2⌋), at which point the element now on top is exactly the middle one: pop it and simply don't restore it. As the recursion unwinds, every other held-aside value gets pushed back, restoring the stack's original order everywhere except at the one position that was dropped. No index is ever computed or used — the recursion counts its way there using only push and pop.
O(n)O(n) call-stack space, no explicit auxiliary structure1class Solution {
2 public int[] deleteMiddleRecursive(int[] stack) {
3 List<Integer> list = new ArrayList<>();
4 for (int x : stack) list.add(x);
5 deleteHelper(list, 0, list.size());
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 deleteHelper(List<Integer> s, int curr, int n) {
12 if (curr == n / 2) {
13 s.remove(s.size() - 1);
14 return;
15 }
16 int top = s.remove(s.size() - 1);
17 deleteHelper(s, curr + 1, n);
18 s.add(top);
19 }
20}