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 - Recursive (Brute Force)

You are climbing a staircase that takes n steps to reach the top. Each time you can climb 1 or 2 steps. Count the distinct number of ways to reach the top. This is essentially the Fibonacci sequence: ways(n) = ways(n-1) + ways(n-2). The brute force approach uses plain recursion, recomputing overlapping subproblems.

TimeComplexity: O(2^n)

SpaceComplexity: O(n)

""" 0070.1 - Climbing Stairs - Solution 1 - Recursive (Brute Force) """

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

    def climbStairs(self, n: int) -> int:
        """Climbing Stairs Function"""
        if n <= 2:
            return n
        return self.climbStairs(n - 1) + self.climbStairs(n - 2)


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().climbStairs(2))   # Expected: 2
    print(Solution().climbStairs(3))   # Expected: 3
    print(Solution().climbStairs(5))   # Expected: 8


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

Solution 2 - Memoization (Top-Down DP)

Same recursive logic but we cache previously computed results in a dictionary to avoid redundant work. Each subproblem is solved only once.

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 0070.2 - Climbing Stairs - Solution 2 - Memoization (Top-Down DP) """

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

    def climbStairs(self, n: int) -> int:
        """Climbing Stairs Function"""
        memo = {}

        def helper(n: int) -> int:
            if n <= 2:
                return n
            if n in memo:
                return memo[n]
            memo[n] = helper(n - 1) + helper(n - 2)
            return memo[n]

        return helper(n)


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().climbStairs(2))   # Expected: 2
    print(Solution().climbStairs(3))   # Expected: 3
    print(Solution().climbStairs(5))   # Expected: 8


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

Solution 3 - Bottom-Up DP (Tabulation)

Build the solution iteratively from the base cases up. We fill a DP array where dp[i] represents the number of ways to reach step i. Each step is the sum of the two preceding steps.

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 0070.3 - Climbing Stairs - Solution 3 - Bottom-Up DP (Tabulation) """

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

    def climbStairs(self, n: int) -> int:
        """Climbing Stairs Function"""
        if n <= 2:
            return n
        dp = [0] * (n + 1)
        dp[1] = 1
        dp[2] = 2
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().climbStairs(2))   # Expected: 2
    print(Solution().climbStairs(3))   # Expected: 3
    print(Solution().climbStairs(5))   # Expected: 8


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

Solution 4 - Space-Optimized DP

Since we only ever need the last two values, we can replace the entire DP array with just two variables. This gives us optimal O(1) space while keeping O(n) time.

TimeComplexity: O(n)

SpaceComplexity: O(1)

""" 0070.4 - Climbing Stairs - Solution 4 - Space-Optimized DP """

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

    def climbStairs(self, n: int) -> int:
        """Climbing Stairs Function"""
        if n <= 2:
            return n
        prev2, prev1 = 1, 2
        for _ in range(3, n + 1):
            curr = prev1 + prev2
            prev2 = prev1
            prev1 = curr
        return prev1


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().climbStairs(2))   # Expected: 2
    print(Solution().climbStairs(3))   # Expected: 3
    print(Solution().climbStairs(5))   # Expected: 8


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

0070 - Climbing Stairs