101
0/320
Loading content...
Design and implement a specialized stack data structure that supports standard stack operations along with the ability to retrieve the smallest element currently stored in the stack—all in constant time complexity.
Your task is to implement the SmallestTracker class with the following methods:
SmallestTracker() — Initializes an empty stack object.void insert(int val) — Inserts the element val onto the top of the stack.void remove() — Removes and discards the element from the top of the stack.int peek() — Returns the element currently at the top of the stack without removing it.int smallest() — Returns the smallest element currently present in the stack.Critical Requirement: Each of these operations must execute in O(1) time complexity. This means that regardless of how many elements are in the stack, every operation should complete in constant time.
The challenge lies in maintaining the minimum value efficiently: a naive approach would require scanning all elements to find the minimum (O(n) time), but you must design a solution that tracks this information in a way that supports O(1) retrieval even after arbitrary sequences of insertions and removals.
operations = ["SmallestTracker","insert","insert","insert","smallest","remove","peek","smallest"]
values = [[],[-2],[0],[-3],[],[],[],[]][null,null,null,null,-3,null,0,-2]SmallestTracker tracker = new SmallestTracker(); tracker.insert(-2); // Stack: [-2] tracker.insert(0); // Stack: [-2, 0] tracker.insert(-3); // Stack: [-2, 0, -3] tracker.smallest(); // Returns -3 (smallest element in stack) tracker.remove(); // Removes -3, Stack: [-2, 0] tracker.peek(); // Returns 0 (top element) tracker.smallest(); // Returns -2 (new smallest after removal)
operations = ["SmallestTracker","insert","insert","peek","smallest"]
values = [[],[5],[10],[],[]][null,null,null,10,5]SmallestTracker tracker = new SmallestTracker(); tracker.insert(5); // Stack: [5] tracker.insert(10); // Stack: [5, 10] tracker.peek(); // Returns 10 (top element) tracker.smallest(); // Returns 5 (smallest element in stack)
operations = ["SmallestTracker","insert","insert","insert","remove","smallest","remove","smallest"]
values = [[],[1],[2],[0],[],[],[],[]][null,null,null,null,null,1,null,1]SmallestTracker tracker = new SmallestTracker(); tracker.insert(1); // Stack: [1] tracker.insert(2); // Stack: [1, 2] tracker.insert(0); // Stack: [1, 2, 0] tracker.remove(); // Removes 0, Stack: [1, 2] tracker.smallest(); // Returns 1 (smallest after 0 was removed) tracker.remove(); // Removes 2, Stack: [1] tracker.smallest(); // Returns 1 (only element left)
Constraints