5 Best Ways to Check if a Sorted Array Can Be Divided in Pairs Whose Sum is K in Python

Rate this post

πŸ’‘ Problem Formulation: The task is to determine whether a sorted array of integers can be divided into pairs such that the sum of each pair is equal to a given value k. For example, given an array [1, 2, 3, 4] and a sum k=5, the array can be divided into pairs (1, 4) and (2, 3) since both pairs sum up to 5.

Method 1: Using a Hashtable

This method involves using a hashtable (dictionary in Python) to keep track of the elements that have already been paired. It iterates through the sorted array, checking for the complement that would make up the sum k and marking paired elements in the hashtable.

Here’s an example:

def can_divide_into_pairs(arr, k):
    seen = {}
    for num in arr:
        if k - num in seen:
            seen[k - num] -= 1
            if seen[k - num] == 0:
                del seen[k - num]
        else:
            seen[num] = seen.get(num, 0) + 1
    return len(seen) == 0

# Example usage
print(can_divide_into_pairs([1, 2, 3, 4], 5))

Output: True

The function can_divide_into_pairs iterates through the sorted array, checking for pairs that sum up to k. The hashtable seen acts as a counter for the number of times a number appears in the array that has not yet been paired. If the function returns True, it means all numbers have been paired successfully; otherwise, it returns False.

Method 2: Two-pointers Technique

This approach utilizes the two pointers technique, which places one pointer at the start and another at the end of the array. By moving the pointers toward the center based on whether the current sum is less than or greater than k, it determines if the array can be paired up.

Here’s an example:

def can_pair_with_two_pointers(arr, k):
    left = 0
    right = len(arr) - 1
    while left < right:
        current_sum = arr[left] + arr[right]
        if current_sum == k:
            left += 1
            right -= 1
        elif current_sum < k:
            left += 1
        else:
            right -= 1
    return left == right

# Example usage
print(can_pair_with_two_pointers([1, 2, 3, 4], 5))

Output: True

The can_pair_with_two_pointers function works by moving the left and right pointers towards each other, checking for pairs that form the desired sum k. If the pointers meet in the middle, it indicates that all elements have been paired successfully.

Method 3: Greedy Algorithm with Pairs Verification

This employs a greedy strategy to pair consecutive elements in the sorted array. It assumes that since the array is sorted, the smallest and the next smallest number pair up to the smallest sum, and so on. This continues unless a pair does not sum to k, in which case the function returns False.

Here’s an example:

def has_pairs_with_sum_k(arr, k):
    for i in range(0, len(arr), 2):
        if arr[i] + arr[i+1] != k:
            return False
    return True

# Example usage
print(has_pairs_with_sum_k([1, 4, 2, 3], 5))

Output: False

The function has_pairs_with_sum_k iteratively checks every consecutive pair in the sorted list. If any pair does not sum to k, it returns False, otherwise, it returns True, signifying that all pairs satisfy the condition.

Method 4: Recursive Pairing

Recursion can be used to solve this problem by successively removing paired numbers from the array and recursively checking the remaining array. Each recursive call focuses on the current smallest number and its complement required to reach the sum k.

Here’s an example:

def pair_recursive(arr, k):
    if not arr:
        return True
    if arr[0] + arr[-1] != k: 
        return False
    return pair_recursive(arr[1:-1], k)

# Example usage
print(pair_recursive([1, 2, 3, 4], 5))

Output: True

The pair_recursive method employs a classic recursive pattern, consistently pairing up the first and last values of the current list and invoking itself on the reduced array without those paired numbers. It returns True if all pairs are found and False if any mismatch occurs.

Bonus One-Liner Method 5: Using List Comprehension and all() Function

A one-liner in Python can check if a sorted array can be divided into pairs summing to k by using list comprehension along with the all() function to ensure every adjacent pair in a sliced and zipped array sums up to the given value.

Here’s an example:

can_pair_one_liner = lambda arr, k: all(x + y == k for x, y in zip(arr[::2], arr[1::2]))
# Example usage
print(can_pair_one_liner([1, 2, 3, 4], 5))

Output: True

The one-liner uses a lambda function to create a generator that iteratively takes slices of the array two elements at a time and checks if their sum equals k. The all() function ensures that all pairs satisfy the condition.

Summary/Discussion

  • Method 1: Hashtable. Efficient for unsorted arrays. Relies on complementary values. May need extra space for hashtable.
  • Method 2: Two-pointers Technique. Efficient. Only works with sorted arrays. Straightforward implementation.
  • Method 3: Greedy Algorithm with Pairs Verification. Quick for checking consecutive elements. Requires array to be pre-sorted to function correctly.
  • Method 4: Recursive Pairing. More elegant but could be less efficient due to overhead of recursive calls. Easy to understand but not suitable for large arrays.
  • Bonus One-Liner Method 5: Compact and uses Python’s advanced features. However, less readable and may be difficult to debug or extend.