Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0155 - Min Stack
    0155 - Min Stack
    0155 - Min Stack
    0155 - Min Stack

    0155 - Min Stack

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/min-stack/

    Solution 1 - Brute Force

    Iterate through every pair of numbers using two nested loops. For each pair, check if they sum to the target. Return the indices when a match is found.

    TimeComplexity:O(n2)TimeComplexity: O(n^2)TimeComplexity:O(n2)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)

    Solution 2 - Brute Force using enumerate()

    Same brute force logic, but uses Python's enumerate() for cleaner index tracking instead of range(len(...)).

    TimeComplexity:O(n2)TimeComplexity: O(n^2)TimeComplexity:O(n2)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)

    Solution 1 - Two Stacks

    Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Use two stacks: one main stack for all values and an auxiliary min stack that tracks the current minimum. On each push, also push onto the min stack if the value is less than or equal to the current minimum. On each pop, pop from the min stack if the popped value equals the current minimum.

    TimeComplexity:O(1)TimeComplexity: O(1)TimeComplexity:O(1)
    SpaceComplexity:O(n)SpaceComplexity: O(n)SpaceComplexity:O(n)

    Solution 2 - Single Stack with Tuples

    Instead of maintaining a separate min stack, store tuples of (value, current_min) on each push. Each entry remembers the minimum at the time it was pushed, so getMin simply reads the second element of the top tuple.

    TimeComplexity:O(1)TimeComplexity: O(1)TimeComplexity:O(1)
    SpaceComplexity:O(n)SpaceComplexity: O(n)SpaceComplexity:O(n)
    """ 0001.1 - Solution 1 - Brute Force Approach """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        """Two Sum Function"""
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().twoSum([3, 3], 6))
    print(Solution().twoSum([3, 2, 4], 6))
    print(Solution().twoSum([2, 7, 11, 15], 9))


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

    """ 0001.1 - Solution 1 - Using Enumerate """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        """Two Sum Function"""
        for key1, num1 in enumerate(nums):
            for key2, num2 in enumerate(nums[key1 + 1 :], key1 + 1):
	              # enumerate(iterable, start=1) -> start value determines starting index
                # Printing value and key will output 1 i , 2 j, 3 k, 4 l 
                if num1 + num2 == target:
                    return [key1, key2]


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().twoSum([3, 3], 6))
    print(Solution().twoSum([3, 2, 4], 6))
    print(Solution().twoSum([2, 7, 11, 15], 9))


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

    """ 0155.1 - Min Stack - Solution 1 - Two Stacks """

#####################################################################################
# Imports
#####################################################################################
# No imports needed

#####################################################################################
# Classes
#####################################################################################
class MinStack:
    """Min Stack Class"""

    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        """Push Function"""
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self) -> None:
        """Pop Function"""
        if self.stack[-1] == self.min_stack[-1]:
            self.min_stack.pop()
        self.stack.pop()

    def top(self) -> int:
        """Top Function"""
        return self.stack[-1]

    def getMin(self) -> int:
        """Get Min Function"""
        return self.min_stack[-1]


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    obj = MinStack()
    obj.push(-2)
    obj.push(0)
    obj.push(-3)
    print(obj.getMin())  # -3
    obj.pop()
    print(obj.top())     # 0
    print(obj.getMin())  # -2


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

    """ 0155.2 - Min Stack - Solution 2 - Single Stack with Tuples """

#####################################################################################
# Imports
#####################################################################################
# No imports needed

#####################################################################################
# Classes
#####################################################################################
class MinStack:
    """Min Stack Class"""

    def __init__(self):
        self.stack = []  # Each element is (value, current_min)

    def push(self, val: int) -> None:
        """Push Function"""
        current_min = min(val, self.stack[-1][1] if self.stack else val)
        self.stack.append((val, current_min))

    def pop(self) -> None:
        """Pop Function"""
        self.stack.pop()

    def top(self) -> int:
        """Top Function"""
        return self.stack[-1][0]

    def getMin(self) -> int:
        """Get Min Function"""
        return self.stack[-1][1]


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    obj = MinStack()
    obj.push(-2)
    obj.push(0)
    obj.push(-3)
    print(obj.getMin())  # -3
    obj.pop()
    print(obj.top())     # 0
    print(obj.getMin())  # -2


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()