Delete Middle Element of a Stack — Editorial

Opening the reading…

Intuitionthe array representation exposes both operations

The input is not written in display order: index 0 is the bottom of the stack, and the last index is the top. Because the problem identifies the middle using the original bottom-to-top order, the element to remove is directly at index (n - 1) / 2. Integer division performs the required floor operation, including the lower middle choice when n is even.

After removing that element, the surviving values are still arranged from bottom to top. The required answer uses the opposite direction, from top to bottom, so reversing the remaining array completes the conversion. No element needs to be searched for by value; its position is determined entirely by the original size.

Approachremove in the input order, then convert the output order

Store the stack size in n and compute middle as (n - 1) / 2, because the statement gives a zero-based position in the bottom-to-top array and integer division selects the lower central element for even sizes.

Erase the element at middle, because exactly that original position is the required middle and erasing preserves the relative order of every other element.

Reverse the shortened array, because it is still bottom to top while the answer must be top to bottom.

Return the reversed array, because it now contains every original element except the selected middle and presents the survivors in the required display order.

Complexitylinear movement, with a copied working array

MEASURE	BOUND	WHY
Time	O(n)	Erasing from a vector shifts the elements after the removed position, and reversing visits each survivor once. Each operation touches at most n elements, so their total work remains linear.
Space	O(n) extra	The output storage is excluded because it is required output, but the value parameter creates a working copy of the input array. The erase and reverse operations use only constant additional auxiliary space beyond that copy.

Here n is the original stack size.

Annotated solutionC++ · direct array operations · the representation does the indexing work

CPPErase the indexed middle element, reverse the survivors, and return the display order.

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> deleteMiddle(vector<int> s) {
        int middle = (static_cast<int>(s.size()) - 1) / 2;
        s.erase(s.begin() + middle);
        reverse(s.begin(), s.end());
        return s;
    }
};

The order of the last two operations matters conceptually. The index is computed before the erase because it refers to the original stack, while the reversal happens after the erase because the required result describes the shortened stack. The call to erase also shifts later values left, so the relative order is already correct before the final reversal.

The recursive alternativea stack-oriented formulation that trades constant auxiliary space for call frames

You can also model the operation as repeatedly removing the top element, recursing on the smaller stack, and putting that element back unless it is the middle one. With the input stored bottom to top, the top is the last array element. This is a different arrangement of the same linear work, not an optimisation: recursion uses O(n) call-stack space, while the direct vector operations use O(n) here because the method receives its array by value and only O(1) auxiliary space beyond it.

CPPRemove one middle item while unwinding from the top, then reverse the remaining stack.

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
    void removeMiddle(vector<int>& s, int remaining) {
        if (remaining == 1) {
            s.pop_back();
            return;
        }

        int top = s.back();
        s.pop_back();
        removeMiddle(s, remaining - 1);

        if (remaining > 2) {
            s.push_back(top);
        }
    }

public:
    vector<int> deleteMiddle(vector<int> s) {
        removeMiddle(s, static_cast<int>(s.size()));
        reverse(s.begin(), s.end());
        return s;
    }
};