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 - Sorting

Given an integer array nums of 2n integers, group these integers into n pairs (a1, b1), (a2, b2), ..., (an, bn) such that the sum of min(ai, bi) for all i is maximized. Return the maximized sum.

The key insight is that to maximize the sum of minimums, we want to minimize the "waste" in each pair. If we sort the array and pair adjacent elements, the difference between paired elements is minimized. The answer is simply the sum of elements at even indices after sorting.

TimeComplexity: O(n \log n)

SpaceComplexity: O(1)

""" 0561.1 - Array Partition - Solution 1 - Sorting """

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

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

    def arrayPairSum(self, nums: List[int]) -> int:
        """Array Partition Function"""
        nums.sort()
        result = 0
        for i in range(0, len(nums), 2):
            result += nums[i]
        return result


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().arrayPairSum([1, 4, 3, 2]))  # Expected: 4
    print(Solution().arrayPairSum([6, 2, 6, 5, 1, 2]))  # Expected: 9


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

Solution 2 - Sorting with Slicing

Same sorting approach, but uses Python slicing nums[::2] to elegantly select every other element starting from index 0, then sums them directly with sum().

TimeComplexity: O(n \log n)

SpaceComplexity: O(n)

""" 0561.2 - Array Partition - Solution 2 - Sorting with Slicing """

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

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

    def arrayPairSum(self, nums: List[int]) -> int:
        """Array Partition Function"""
        return sum(sorted(nums)[::2])


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().arrayPairSum([1, 4, 3, 2]))  # Expected: 4
    print(Solution().arrayPairSum([6, 2, 6, 5, 1, 2]))  # Expected: 9


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

0561 - Array Partition

Solution 1 - Brute Force

Solution 2 - Brute Force using enumerate()

Solution 1 - Sorting

Solution 2 - Sorting with Slicing

Solution 2 - Brute Force using `enumerate()`