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?

To support an $O(1)$ timeMIN operation without increasing the time complexity of standard stack operations (PUSH and POPmust both remain $O(1)$):

• Option A: By storing with each record in the stack a pointer to the minimum element present at or below that record's position, we can update the pointer during PUSH in $O(1)$ time (comparing the new key with the minimum below it). During POP, the stack simply shrinks, automatically exposing the previous minimum at the new top in $O(1)$ time.MIN simply returns the pointer stored at the top of the stack in $O(1)$ time. Thus, (A) is correct.

• Option B: If only a single global pointer to the current minimum record is maintained, when that minimum record is popped, finding the new minimum requires scanning the remaining elements of the stack, which takes $O(n)$ time and increases the complexity of POP. Thus, (B) is incorrect.

• Option C: Maintaining a sorted auxiliary array requires $O(n)$ time to insert or remove elements, increasing the complexity of PUSH and POPto $O(n)$. Thus,(C) is incorrect.

• Option D: Maintaining a Min-Heap requires $O(\log n)$ time per PUSH (insert) and POP (delete), increasing the complexity of standard stack operations from $O(1)$ to $O(\log n)$. Thus, (D) is incorrect.

Hence, only (A) achieves the required complexities.