155. Min Stack

 

Implementing a MinStack in Java

Stacks are one of the most fundamental data structures in computer science. While their basic functionality allows us to add and remove elements in a Last In First Out (LIFO) order, sometimes we want additional operations for specialized use cases. One common problem is how to efficiently retrieve the minimum element from the stack at any time, alongside standard stack operations like push() and pop().

In this post, we'll walk through the implementation of a MinStack, which not only behaves like a regular stack but also supports constant-time (O(1)) retrieval of the minimum element at any point.

Problem Definition: MinStack

We need to implement a special stack that supports the following operations in constant time:

  • push(int val): Pushes an element onto the stack.
  • pop(): Removes the element on top of the stack.
  • top(): Returns the element on top of the stack.
  • getMin(): Retrieves the minimum element in the stack at any given moment.

The Challenge

The challenge here is ensuring that we can retrieve the minimum value in constant time. Normally, a stack doesn't keep track of the minimum element, and finding it would require scanning the entire stack, which would take O(n) time in the worst case. We need to design our stack to track the minimum in O(1) time without sacrificing the performance of the other operations.

Approach: Two Stacks

To solve this problem efficiently, we'll use two stacks:

  1. A primary stack, stack, that holds all the elements.
  2. A secondary stack, minStack, that stores only the minimum values.

Here’s how it works:

  • When we push a value onto the stack, we compare it with the current minimum (i.e., the top of minStack). If the value is smaller than or equal to the current minimum, we push it onto minStack as well.
  • When we pop a value from the stack, if the popped value is the same as the top of minStack, we pop from minStack too. This ensures that minStack always holds the correct minimum value.

This way, we can always retrieve the minimum element from the top of minStack in constant time.

Code Implementation

class MinStack {
    Stack<Integer> stack = new Stack();
    Stack<Integer> minStack = new Stack();

    public MinStack() {
       
    }
   
    public void push(int val) {
        if(stack.size() == 0) {
            stack.push(val);
            minStack.push(val);
        }else {
            if(minStack.peek() >= val) {
                minStack.push(val);
            }
            stack.push(val);
        }
    }
   
    public void pop() {
        int min = stack.pop();
        if(min == minStack.peek()) {
            minStack.pop();
        }
    }
   
    public int top() {
        return stack.peek();
    }
   
    public int getMin() {
        return minStack.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

Time and Space Complexity

  • Time Complexity: Each operation (push, pop, top, and getMin) takes constant time O(1) because we only push, pop, or peek from stacks, which are O(1) operations.

  • Space Complexity: In the worst case, every element is added to both stack and minStack, so the space complexity is O(n), where n is the number of elements in the stack.

Conclusion

This two-stack approach efficiently tracks the minimum value in a stack, allowing constant-time retrieval of the minimum while keeping the push and pop operations equally efficient. The key insight is using the minStack to mirror the minimum values at each point in time. This solution is a common interview problem and serves as a great example of how additional data structures can enhance the functionality of fundamental structures like stacks.

Comments

Post a Comment

Popular posts from this blog

3Sum Closest: O(n²) Two-Pointer Magic šŸš€ leetcode: 16

Three Sum Closest - LeetCode Solution In this blog post, we'll dive into the Three Sum Closest problem, a popular coding challenge on LeetCode. We'll explore the intuition behind the solution, discuss the approach, analyze the complexity, and provide a detailed explanation of the code. Additionally, I'll share my LeetCode solution link for further reference. Problem Statement Given an integer array nums of length n and an integer target , find three integers in nums such that the sum is closest to target . Return the sum of the three integers. You may assume that each input would have exactly one solution. Intuition The problem requires finding three numbers in the array whose sum is as close as possible to the target. To efficiently find such a triplet, we can use a combination of sorting and the two-pointer technique . Sorting : First, sort the array. This allows us to use the two-po...
Read more

Kadane's Algorithm: Maximum Subarray Problem - LeetCode(53) Solution

Maximum Subarray Problem - LeetCode Solution Maximum Subarray Problem - LeetCode Solution Problem Statement Given an integer array nums , find the contiguous subarray (containing at least one number) that has the largest sum and return its sum. Intuition The problem requires finding the contiguous subarray with the maximum sum. A brute force approach would involve checking all subarrays, but this would be inefficient. Instead, we use Kadane's Algorithm , which efficiently finds the maximum sum subarray in O(n) time. Approach Initialize two variables: total (running sum) and maxi (maximum sum encountered so far). Iterate through the array: Add the current element to total . Update maxi with the maximum of maxi and total . If total becomes negative, reset it to zero. Return maxi as the maximum sub...
Read more

LeetCode Problem: Implement pow(x, n) leetcode:- 50

Understanding the Fast Exponentiation Algorithm: Exponentiation by Squaring In this blog post, we will explore the implementation of the myPow function, a common problem found on LeetCode. The goal of this problem is to compute \(x^n\) efficiently, even when \(n\) is a very large number. Instead of using a naive approach, we employ a method called Exponentiation by Squaring to significantly reduce the number of multiplications required. Problem Overview Given a floating-point number x and an integer n , our task is to implement a function that computes \(x^n\). A straightforward solution might involve multiplying x by itself n times, but this approach is too slow when n is large. Intuition Behind Exponentiation by Squaring The main idea is to reduce the problem size by halving the exponent at each recursive step. Consider the following: If n is even, then: \(x^n = x^{...
Read more