Max Number of K-Sum Pairs

Problem

You are given an integer array nums and an integer k. In one operation you may pick two elements of the array whose values add up to exactly k, and remove both of them from the array.

Return the maximum number of such operations you can perform. Each element can be used in at most one operation — once removed, it is gone.

Examples

Example 1

Input:  nums = [1, 2, 3, 4], k = 5
Output: 2

Pair (1, 4) and pair (2, 3) both sum to 5, so two operations are possible.

Example 2

Input:  nums = [3, 1, 3, 4, 3], k = 6
Output: 1

Only one pair of 3s can be removed (3 + 3 = 6); the remaining [1, 4, 3] has no pair summing to 6.

Example 3

Input:  nums = [2, 2, 2, 2], k = 4
Output: 2

The four 2s form two disjoint pairs, each summing to 4.

Constraints

• 1 <= nums.length <= 10^5 — an O(n^2) pairing scan is too slow.
• 1 <= nums[i] <= 10^9
• 1 <= k <= 10^9

Think about it first

TL;DR

Sort + two pointers from both ends, O(n log n) time / O(1) extra space — or a one-pass hash-map count, O(n) time / O(n) space.

Approach 1 — Brute force

For every element, scan the rest of the array for an unused partner that completes the sum, marking both as used when found.

from typing import List

def maxOperations(nums: List[int], k: int) -> int:
    used = [False] * len(nums)
    ops = 0
    for i in range(len(nums)):
        if used[i]:
            continue
        for j in range(i + 1, len(nums)):
            if not used[j] and nums[i] + nums[j] == k:
                used[i] = used[j] = True
                ops += 1
                break
    return ops

Complexity: O(n^2) time, O(n) space. With n up to 10^5, n^2 = 10^10 comparisons — far past the time limit.

Approach 2 — Sort + two pointers

After sorting, the smallest and largest remaining values bracket every possible pair sum. If nums[left] + nums[right] < k, then nums[left] is too small to pair with anything still available (the right pointer is already at the largest remaining value), so left can be discarded. Symmetrically, if the sum is too large, nums[right] can never be used. If the sum equals k, take the pair; because each value can only pair with k minus itself, matching the two extremes never blocks a better pairing.

flowchart TD
    A["left = 0, right = n - 1"] --> B{"left < right?"}
    B -- no --> E["return ops"]
    B -- yes --> C{"nums[left] + nums[right] vs k"}
    C -- "equals k" --> D["ops += 1; left++, right--"]
    C -- "less than k" --> F["left++"]
    C -- "greater than k" --> G["right--"]
    D --> B
    F --> B
    G --> B

from typing import List

def maxOperations(nums: List[int], k: int) -> int:
    nums.sort()
    left, right = 0, len(nums) - 1
    ops = 0
    while left < right:
        total = nums[left] + nums[right]
        if total == k:
            ops += 1
            left += 1
            right -= 1
        elif total < k:
            left += 1
        else:
            right -= 1
    return ops

Walkthrough on nums = [3, 1, 3, 4, 3], k = 6 → sorted [1, 3, 3, 3, 4]:

Answer: 1.

Complexity: O(n log n) time (sorting dominates), O(1) extra space beyond the sort.

Approach 3 — One-pass hash map

Order does not matter here. For each incoming value x, you only need to know whether an unmatched k - x has already been seen. Keep a counter of unmatched values: if a complement is waiting, consume it and count an operation; otherwise record x as waiting. This is the Two Sum hash-map idea extended to multiplicities.

from collections import Counter
from typing import List

def maxOperations(nums: List[int], k: int) -> int:
    waiting: Counter[int] = Counter()
    ops = 0
    for x in nums:
        need = k - x
        if waiting[need] > 0:
            waiting[need] -= 1
            ops += 1
        else:
            waiting[x] += 1
    return ops

Walkthrough on nums = [1, 2, 3, 4], k = 5:

• x = 1: need 4, none waiting → waiting = {1: 1}
• x = 2: need 3, none waiting → waiting = {1: 1, 2: 1}
• x = 3: need 2, one waiting → consume it, ops = 1
• x = 4: need 1, one waiting → consume it, ops = 2

Answer: 2.

Complexity: O(n) time, O(n) space.

Common pitfalls

• Self-pairing when k is even: with the hash map, checking waiting[need] before incrementing waiting[x] is what stops a single element from pairing with itself when x == k - x.
• Double counting: counting every index pair (i, j) with nums[i] + nums[j] == k instead of disjoint pairs — each element may be removed only once.
• Two-pointer equal case: on a match you must move both pointers; moving only one either recounts an element or loops forever.
• Negative complement: when x > k, the complement k - x is negative and won’t be in waiting, which is the correct outcome — no special handling is needed. (The pair sum peaks at 2·10^9, still within a signed 32-bit range, so overflow is not a concern here.)

Pattern takeaway

Sorted two-pointers works whenever an extreme element can be proved dead: if the smallest plus the largest is still short of the target, the smallest can never participate and is safely discarded (and symmetrically for the largest). That discard argument — not the sortedness itself — is what makes the linear sweep correct, and it is the same argument you’ll reuse in Two Sum II and container-style problems.