Problem Statement

Stack with O(1) MIN Data Structures - Augmenting a Stack The following item is from the technical (data structures) section of the Q2 SDE on-campus online assessment. Choose the single best option. Question 1 We wish to augment a standard stack data structure to support a MIN operation that returns a pointer to the record with the smallest key currently present in the stack in O(1) time, without deleting the record and without increasing the O(1) time complexity of the standard PUSH and POP operations. Which of the following approaches successfully accomplishes this objective? Options: Keep a single global pointer to the record with the smallest key in the stack. Keep with every record in the stack a pointer to the record with the smallest key below it. Maintain a Min-Heap alongside the stack containing all key values. Keep an auxiliary array in which the key values of the stack are maintained in sorted order.