170. Find the Middle Element of a Stack

Given a stack of n integers (given as space-separated values from bottom to top), print the value at its physical middle position. If n is even, print the one closer to the top of the two middle elements.

Input: The input is a single line of space-separated integers, the stack's values from bottom to top. Output: Print a single integer - the value at the stack's physical middle position.

1 <= n <= 10^5

This problem is fundamentally about POSITION, not VALUE - a common point of confusion is trying to find the 'middle value' by sorting or comparing values, when the answer is really just about counting positions.

Find the value sitting at the physical middle position of a stack. Brute force: Pop every element into an auxiliary structure, counting as you go, to find the middle one, then push everything back in the original order - this works but requires extra bookkeeping to restore the original stack afterward. Optimised: Since this problem primarily asks you to FIND the value (not necessarily preserve the stack afterward, depending on the exact requirements), a simple index computation (n/2 from the bottom) directly identifies which position to read - the main engineering challenge, if the stack must be preserved, is doing this without a full array copy.

Pop every element off the given stack one at a time into a temporary array, which naturally reverses the order to top-to-bottom. Once all n values are collected, compute which index corresponds to the physical middle using the 'closer to top on ties' rule and print that value. This is simple to reason about but spends extra memory rebuilding the whole stack as an array just to read one value. Time: O(n) Space: O(n)

Recursively pop elements off the stack one by one, using the recursion depth itself as a counter of how many elements have been removed so far. When the count reaches the required middle position (measured from the top, adjusted for the even/odd rule), record that value, then as the recursion unwinds push every popped element back in its original order. This avoids building a separate array, using the call stack as the only extra storage. Time: O(n) Space: O(n) (recursion stack)

Since the stack's n values are already given in bottom-to-top order, the 'physical middle' is just a specific index into that sequence, computable directly with a formula (using floor/ceil based on whether n is even, favoring the element closer to the top). No stack simulation, pushing, or popping is needed at all - simply compute the index once and print the corresponding value while reading the input. This removes all auxiliary data-structure overhead. Time: O(n) (just to read input) Space: O(1) extra

1. Recognize that 'middle' here means POSITION (counting from the bottom), not value. 2. The middle element sits at index n/2 (using integer division), counting from the bottom (0-indexed). 3. For an even-sized stack, this same formula naturally lands on the one closer to the top.

Time: O(n) - some form of traversal (or two-pointer approach counting from both ends) is needed to reach the middle position. Space: O(n) if using an auxiliary structure to preserve the original stack, or O(1) if the stack doesn't need to be preserved.

n = 1 (the single element is trivially the middle); an even n, where the element closer to the top of the two middle ones is printed (per the hints); n = 10^5 for performance.

Be ready to mention a doubly-linked-list-based stack implementation with a maintained 'middle pointer' (updated incrementally on every push/pop) as an O(1)-per-operation alternative, if this exact query needs to be answered repeatedly and efficiently.