Question

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 the 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?

• A. Keep with every record in the stack, a pointer to the record with the smallest key below it.
• B. Keep a pointer to the record with the smallest key in the stack.
• C. Keep an auxiliary array in which the key values of the records in the stack are maintained in sorted order.
• D. Keep a Min-Heap in which the key values of the records in the stack are maintained.

Hint:

{To maintain the minimum efficiently in a stack, track the smallest element at each level using auxiliary pointers.}

Answer 1

The Correct Option is A

- To ensure \( O(1) \) time complexity for the MIN operation, each element in the stack can store an additional pointer to the smallest key below it. This allows for constant time retrieval of the minimum element.

- This method enables the MIN operation to be performed in \( O(1) \) time without modifying the standard stack operations, which is the key advantage of Option (A).

- Option (B) fails because updating the minimum pointer would require a traversal of the stack, resulting in \( O(n) \) time complexity in the worst case. This defeats the purpose of achieving \( O(1) \) time for the MIN operation.

- Options (C) and (D) involve sorting or maintaining auxiliary data structures, which increases the time complexity beyond \( O(1) \), making them unsuitable for efficient minimum retrieval in this context.

Thus, the correct option is (A).