What is the time complexity of Min Stack?

The optimal solution has a time complexity of O(1).

What data structures are used to solve Min Stack?

This problem uses Stack, Design. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Min Stack?

Insight 1: Maintaining a separate stack to keep track of the minimum elements at each point of time. Insight 2: When pushing an element, compare it with the current minimum. If the new element is less than or equal to the current minimum, push it onto the min_stack.

Which companies ask LeetCode 155. Min Stack in interviews?

This problem is frequently asked at Cisco, Delhivery, IMC, Informatica, Intuit and 21 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Min Stack - LeetCode 155 Solution

Min Stack - Complete Solution Guide

Min Stack is LeetCode problem 155, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement the MinStack class: MinStack() initializes the stack object. void push(int val) pushes the element val onto the stack. void pop() removes the element on the top of the stack. int top() gets the top element of the stack. int getMin() retrieves the minimum element in the stack. You must implement a solution with O(1) time complexity for each function. Example 1: Input ["MinStack","push","pus

Detailed Explanation

The problem requires designing a stack data structure with the additional functionality of retrieving the minimum element in O(1) time. The stack needs to support the standard `push`, `pop`, and `top` operations, along with a `getMin` operation. The input will be a series of calls to these operations on the `MinStack` object. The output will be the return values of the `top` and `getMin` operations, and `null` for `push` and `pop`.

Solution Approach

The solution uses two stacks: one for the main stack and another for tracking the minimum elements. When an element is pushed onto the main stack, it's also compared to the top of the min_stack. If the new element is less than or equal to the current minimum (top of min_stack), it's also pushed onto the min_stack. When an element is popped from the main stack, it's compared to the top of the min_stack. If they are equal, the top element is also popped from the min_stack. The `top` operation returns the top element of the main stack, and the `getMin` operation returns the top element of the min_stack. This allows for constant-time retrieval of the minimum element.

Step-by-Step Algorithm

Step 1: Initialize two stacks: `stack` to store all elements and `min_stack` to store minimum elements.
Step 2: In the `push` operation, push the given value `val` onto the `stack`.
Step 3: In the `push` operation, if `min_stack` is empty or `val` is less than or equal to the current minimum (top of `min_stack`), push `val` onto the `min_stack`.
Step 4: In the `pop` operation, pop the top element from the `stack`.
Step 5: In the `pop` operation, if the popped element from `stack` is equal to the top element of `min_stack`, pop the top element from `min_stack`.
Step 6: In the `top` operation, return the top element of the `stack`.
Step 7: In the `getMin` operation, return the top element of the `min_stack`.

Key Insights

Insight 1: Maintaining a separate stack to keep track of the minimum elements at each point of time.
Insight 2: When pushing an element, compare it with the current minimum. If the new element is less than or equal to the current minimum, push it onto the min_stack.
Insight 3: During pop operation, check if the element being popped from the main stack is equal to the top of the min_stack. If it is, pop from the min_stack as well. The equals comparison is important for cases where multiple identical min values exist.

Complexity Analysis

Time Complexity: O(1)

Space Complexity: O(n)

Topics

This problem involves: Stack, Design.

Companies

Asked at: Cisco, Delhivery, IMC, Informatica, Intuit, LinkedIn, Lucid, Lyft, MakeMyTrip, Morgan Stanley, Nike, Nvidia, Odoo, Oracle, Palo Alto Networks, PayPal, Paytm, Salesforce, Snap, Snowflake, Tinkoff, Veeva Systems, Vimeo, Walmart Labs, Yandex, Zenefits.

Min Stack | LeetCode 155

Medium

Stack Design

Time: O(1)Space: O(n)

Solution Code

Available in:

import java.util.ArrayList;
import java.util.List;

class MinStack {

    private List<Integer> stack;
    private List<Integer> minStack;

    public MinStack() {
        this.stack = new ArrayList<>();
        this.minStack = new ArrayList<>();
    }

    public void push(int val) {
        this.stack.add(val);
        if (this.minStack.isEmpty() || val <= this.minStack.get(this.minStack.size() - 1)) {
            this.minStack.add(val);
        }
    }

    public void pop() {
        if (this.stack.remove(this.stack.size() - 1).equals(this.minStack.get(this.minStack.size() - 1))) {
            this.minStack.remove(this.minStack.size() - 1);
        }
    }

    public int top() {
        return this.stack.get(this.stack.size() - 1);
    }

    public int getMin() {
        return this.minStack.get(this.minStack.size() - 1);
    }
}

/**
 * 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();
 */

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 155: Min Stack - Detailed explanation and solution approaches.

Topics

Stack Design

Companies

CiscoDelhiveryIMCInformaticaIntuitLinkedInLucidLyft

Stats

Difficulty:Medium

Languages:4

Companies:26

Problem #:155

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

7 steps

1
Step 1: Initialize two stacks: `stack` to store all elements and `min_stack` to store minimum elements.
2
Step 2: In the `push` operation, push the given value `val` onto the `stack`.
3
Step 3: In the `push` operation, if `min_stack` is empty or `val` is less than or equal to the current minimum (top of `min_stack`), push `val` onto the `min_stack`.
4
Step 4: In the `pop` operation, pop the top element from the `stack`.
5
Step 5: In the `pop` operation, if the popped element from `stack` is equal to the top element of `min_stack`, pop the top element from `min_stack`.
6
Step 6: In the `top` operation, return the top element of the `stack`.
7
Step 7: In the `getMin` operation, return the top element of the `min_stack`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(1)

⚡ Constant time - Super fast! Same speed regardless of input size.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is O(1) because each operation involves at most a few constant-time operations like stack pushes, pops, and comparisons. The space complexity is O(n) because, in the worst case, the `min_stack` could potentially store as many elements as the main `stack`.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Using a single stack with pairs

Store each element in the stack along with the minimum value seen so far. This approach uses only one stack, but the space complexity remains the same.

Time: O(1) for all operations.Space: O(n)

Trade-offs: This approach uses a single stack but may have a slightly higher constant factor due to storing pairs of values.

✨

Key Insights

1Insight 1: Maintaining a separate stack to keep track of the minimum elements at each point of time.
2Insight 2: When pushing an element, compare it with the current minimum. If the new element is less than or equal to the current minimum, push it onto the min_stack.
3Insight 3: During pop operation, check if the element being popped from the main stack is equal to the top of the min_stack. If it is, pop from the min_stack as well. The equals comparison is important for cases where multiple identical min values exist.

📚

Key Terms Explained

For Students

Stack

LIFO structure - Last In, First Out. Like a stack of plates!

Edge Cases

Edge case 1: Pushing a value that is equal to the current minimum. This is handled correctly because the code pushes the new value onto the `min_stack` if it's less than or equal to the current minimum.
Edge case 2: Popping the minimum value. The code checks if the popped element from the main stack is equal to the current minimum (top of `min_stack`) and, if so, also pops the minimum from the `min_stack`.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Failing to consider the case where the value being pushed is equal to the current minimum. This can lead to the `min_stack` not being updated correctly, causing `getMin` to return an incorrect value.

✗Common mistake 2: Forgetting to pop from the `min_stack` when popping the minimum element from the main `stack`. This can lead to the `min_stack` containing stale minimum values.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Tracking the minimum price of a stock over time. This data structure efficiently allows for finding the current minimum price.

🏦Real-world scenario 2: Implementing an undo/redo feature in a text editor with constraints. The `min_stack` could store the minimum number of keystrokes to reach a particular state.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Stacks are perfect for problems involving matching (parentheses) or "next greater element" patterns. If you need to look back at recent elements, think stack.

🎯 Interview Tip

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ Watch Out

Popping from an empty stack. Always check if the stack is non-empty before popping.

👨‍💻 From Experience

This problem pattern appears frequently in real codebases. I've used similar logic when building production systems.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: November 3, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 14

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 7

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJun 30

❓

Frequently Asked Questions

What is a monotonic stack and when should I use it?

A monotonic stack maintains elements in sorted order (increasing or decreasing). Use it for "next greater element," "largest rectangle," or "stock span" problems. It achieves O(n) time by avoiding redundant comparisons through maintaining order invariants.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Min Stack"?

For this medium-level Stack problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether design techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?