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 - Kadane's Algorithm

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum, and return its sum. Kadane's Algorithm works by iterating through the array and at each position deciding whether to extend the current subarray or start a new one. We track the maximum sum seen so far.

TimeComplexity: O(n)

SpaceComplexity: O(1)

""" 0053.1 - Maximum Subarray - Solution 1 - Kadane's Algorithm """

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

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

    def maxSubArray(self, nums: List[int]) -> int:
        """Maximum Subarray Function"""
        max_sum = nums[0]
        current_sum = nums[0]

        for i in range(1, len(nums)):
            current_sum = max(nums[i], current_sum + nums[i])
            max_sum = max(max_sum, current_sum)

        return max_sum


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # 6
    print(Solution().maxSubArray([1]))                                # 1
    print(Solution().maxSubArray([5, 4, -1, 7, 8]))                  # 23
    print(Solution().maxSubArray([-1]))                               # -1
    print(Solution().maxSubArray([-2, -1]))                           # -1


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

Solution 2 - Brute Force (Check All Subarrays)

Iterate through every possible subarray using two nested loops. For each starting index, accumulate the running sum and track the maximum. This guarantees correctness but is slower.

TimeComplexity: O(n^2)

SpaceComplexity: O(1)

""" 0053.2 - Maximum Subarray - Solution 2 - Brute Force """

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

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

    def maxSubArray(self, nums: List[int]) -> int:
        """Maximum Subarray Function"""
        max_sum = nums[0]

        for i in range(len(nums)):
            current_sum = 0
            for j in range(i, len(nums)):
                current_sum += nums[j]
                max_sum = max(max_sum, current_sum)

        return max_sum


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # 6
    print(Solution().maxSubArray([1]))                                # 1
    print(Solution().maxSubArray([5, 4, -1, 7, 8]))                  # 23
    print(Solution().maxSubArray([-1]))                               # -1
    print(Solution().maxSubArray([-2, -1]))                           # -1


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

0053 - Maximum Subarray

Solution 1 - Brute Force

Solution 2 - Brute Force using enumerate()

Solution 1 - Kadane's Algorithm

Solution 2 - Brute Force (Check All Subarrays)

Solution 2 - Brute Force using `enumerate()`