K-Complementary Pairs

Find all pairs in an array that sum to a target K, the classic "two-sum" variant that comes up constantly in feature engineering and data validation.

Problem

Given an array A and an integer K, count all ordered pairs (i, j) where A[i] + A[j] == K.

Example: A = [1, 5, 3, 4, 2], K = 6 Pairs: (1,5), (5,1), (3,3), (4,2), (2,4), but as unordered unique pairs: {1,5}, {4,2}, {3,3}.

Approach

1. Build a frequency map counting occurrences of each value.
2. For each element, compute its complement (K - num) and check the map.
3. Accumulate the count of valid pairings, then divide by 2 to avoid double-counting unordered pairs.
4. Handle the special case where a number is its own complement (2 * num == K).

Using a hash map gives us O(1) lookups instead of the O(n) inner loop of the brute-force approach.

Implementation

from collections import defaultdict

def find_k_complementary_pairs(arr, K):
    count = defaultdict(int)
    for num in arr:
        count[num] += 1

    pairs = 0
    for num in count:
        complement = K - num
        if complement in count:
            if complement == num:
                pairs += count[num] * (count[num] - 1)
            else:
                pairs += count[num] * count[complement]

    return pairs // 2


A = [1, 2, 3, 4, 5, 6]
K = 7
print(find_k_complementary_pairs(A, K))  # 3 pairs: (1,6), (2,5), (3,4)

Complexity

• Time: O(n), two linear passes over the array
• Space: O(n), for the frequency map

Takeaway

The hash-map complement lookup is the backbone of two-sum problems. Once you internalize this pattern, you'll reach for it whenever you need to find pairs satisfying some constraint.

---

Back to Algorithms & Data Structures