Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0561 - Array Partition
    0561 - Array Partition
    0561 - Array Partition
    0561 - Array Partition

    0561 - Array Partition

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/array-partition/

    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 - 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(nlog⁡n)TimeComplexity: O(n \log n)TimeComplexity:O(nlogn)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)

    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(nlog⁡n)TimeComplexity: O(n \log n)TimeComplexity:O(nlogn)
    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()

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

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