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(n^2)

SpaceComplexity: O(1)

""" 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()

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(n^2)

SpaceComplexity: O(1)

""" 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()

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)

SpaceComplexity: O(n)

""" 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()

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)

SpaceComplexity: O(n)

""" 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()

0155 - Min Stack

Solution 1 - Brute Force

Solution 2 - Brute Force using enumerate()

Solution 1 - Two Stacks

Solution 2 - Single Stack with Tuples

Solution 2 - Brute Force using `enumerate()`