Consider a stack data structure into which we can PUSH and POP records. Assume that each record pushed in the stack has a positive integer key and that all keys are distinct. We wish to augment the stack data structure with an O(1) time MIN operation that returns a pointer to the record with smallest key present in the stack

1. without deleting the corresponding record, and
2. without increasing the complexities of the standard stack operations.

Which one or more of the following approach(es) can achieve it?

The correct option is: Keep with every record in the stack, a pointer to the record with the smallest key below it.

To understand why this approach is correct and meets all the constraints, let's analyze the requirements and how each stack operation ($\mathrm{PUSH}$, $\mathrm{POP}$, and $\mathrm{MIN}$) behaves under this scheme.

1. Analyzing the Proposed Approach:
When we push a record onto the stack, we store along with it a pointer. This pointer points to the record in the stack (at or below the current record) that has the minimum key.

2. How standard operations are implemented in $O\left(1\right)$ time:
Let $R$ be the new record we want to push onto the stack, and let $T$ be the current top record of the stack before the push.

For a $\mathrm{PUSH}\left(R\right)$ operation:
- If the stack is currently empty, the minimum record in the stack is $R$ itself. We set $R$'s minimum pointer to point to $R$.
- If the stack is not empty, the minimum element below $R$ is already tracked by the top record $T$'s minimum pointer. Let this record be $M=T\to \mathrm{min\_ptr}$.
- We compare the key of $R$ with the key of $M$.
- If $\mathrm{key}\left(R\right)<\mathrm{key}\left(M\right)$, then $R$ is the new minimum, so we set $R\to \mathrm{min\_ptr}=R$.
- Otherwise, $M$ remains the minimum, so we set $R\to \mathrm{min\_ptr}=M$.
Since this only requires a single comparison and pointer assignment, the $\mathrm{PUSH}$ operation takes $O\left(1\right)$ time.

For a $\mathrm{POP}\left(\right)$ operation:
- We simply remove the top record from the stack.
- Since each record maintains its own independent pointer to the minimum element below it, removing the top record does not affect or invalidate the minimum pointers of any records remaining in the stack.
- Thus, the $\mathrm{POP}$ operation also takes $O\left(1\right)$ time.

For the $\mathrm{MIN}\left(\right)$ operation:
- To find the minimum key in the stack, we look at the top record of the stack, say $T$, and return its minimum pointer: $T\to \mathrm{min\_ptr}$.
- This is a simple pointer retrieval, which executes in $O\left(1\right)$ time without deleting any records.

3. Why other approaches fail to meet the constraints:
- Keeping a single pointer to the record with the smallest key in the stack: While $\mathrm{MIN}$ and $\mathrm{PUSH}$ could be handled in $O\left(1\right)$, a $\mathrm{POP}$ operation that removes the minimum element would force us to search the entire stack to find the next minimum, taking $O\left(n\right)$ time.
- Keeping an auxiliary sorted array or a Min-Heap: Maintaining these auxiliary structures requires updating them during $\mathrm{PUSH}$ and $\mathrm{POP}$ operations. Inserting or deleting from a sorted array takes $O\left(n\right)$ time, and doing so in a Min-Heap takes $O(\log n)$ time, both of which increase the complexity of standard stack operations beyond $O\left(1\right)$.