Implement Min Stack
Learning DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Implementing a Min Stack with O(2N) and O(N) Space Complexity Approaches, Stack, Data Structures, Time Complexity, Space Complexity, Big O Notation, complexity analysis, space optimization, encoding, stack, Data Structure Operations, Algorithm Analysis.
Problem Statement Design a stack that supports push, pop, top, and getMin operations, all in constant time. The getMin operation should retrieve the minimum element currently in the stack. Input Format The input will consist of a sequence of operations. Each operation will be provided as a string, and for push operations, an integer value will follow. The operations will be encapsulated within lists. Output Format The output should be a list of results corresponding to the getMin and top operations. For push and pop operations, the result will be null. Example Input: ["MinStack", "push", "push", "push", "getMin", "pop", "top", "getMin"] [[], [ 2], [0], [ 3], [], [], [], []] Output: [null, null, null, null, 3, null, 0, 2] Explanation: 1. MinStack: Initializes an empty stack. 2. push( 2): Stack: [ 2] (Min: 2) 3. push(0): Stack: [ 2, 0] (Min: 2) 4. push( 3): Stack: [ 2, 0, 3] (Min: 3) 5. getMin(): Returns 3. 6. pop(): Stack: [ 2, 0] (Min: 2). Top element 3 is removed. 7. top(): Returns 0. 8. getMin(): Returns 2.