Problem Description

You have an array of integers nums and a target value k. Your task is to find pairs of numbers in the array that add up to k and remove them. Each pair removal counts as one operation.

The goal is to find the maximum number of operations (pair removals) you can perform on the array.

For example, if nums = [1, 2, 3, 4] and k = 5, you can remove the pairs (1, 4) and (2, 3) since both pairs sum to 5. This gives you 2 operations total.

Key points:

• Each number in the array can only be used once
• You need to find pairs whose sum equals exactly k
• You want to maximize the number of such pairs you can form
• Once a number is used in a pair, it cannot be reused in another pair

The solution uses a two-pointer approach after sorting the array. By placing pointers at the beginning (l) and end (r) of the sorted array, we can efficiently find pairs:

• If nums[l] + nums[r] == k, we found a valid pair, increment our count and move both pointers inward
• If nums[l] + nums[r] > k, the sum is too large, so move the right pointer left to decrease the sum
• If nums[l] + nums[r] < k, the sum is too small, so move the left pointer right to increase the sum

This approach ensures we find the maximum number of valid pairs in O(n log n) time due to sorting.

Intuition

When looking for pairs that sum to a target value k, we need an efficient way to find matching numbers. Consider what happens when we sort the array first - the smallest numbers are on the left and the largest on the right.

This sorted arrangement gives us a powerful property: if we pick any two positions, we can immediately know whether we need larger or smaller numbers to reach our target. If the sum of two numbers is too large, we know we need a smaller number. Since the array is sorted, all smaller numbers are to the left of our current right position. Similarly, if the sum is too small, all larger numbers are to the right of our current left position.

The two-pointer technique naturally emerges from this observation. We start with the extreme values - the smallest (nums[l]) and largest (nums[r]) numbers. Their sum gives us three possibilities:

1. Perfect match (sum == k): We found a valid pair! Remove both by moving both pointers inward.

2. Sum too large (sum > k): We need a smaller sum. Since we can't get a smaller left value (it's already the smallest available), we must reduce the right value by moving r leftward.

3. Sum too small (sum < k): We need a larger sum. Since we can't get a larger right value (it's already the largest available), we must increase the left value by moving l rightward.

This greedy approach works because once we use a number in a pair, it's optimal to remove it immediately. There's no benefit to "saving" a number for later since each number can only be used once. The sorting ensures we systematically explore all possible pairs while avoiding redundant checks, converging from both ends toward the middle until no more valid pairs can be formed.

Learn more about Two Pointers and Sorting patterns.

Solution Approach

The implementation follows the two-pointer pattern on a sorted array. Here's how the algorithm works step by step:

1. Sort the array: First, we sort nums in ascending order using nums.sort(). This enables the two-pointer technique by arranging elements from smallest to largest.

2. Initialize pointers and counter:

   • Set l = 0 pointing to the leftmost (smallest) element
   • Set r = len(nums) - 1 pointing to the rightmost (largest) element
   • Set ans = 0 to count the number of valid operations

3. Main loop: Continue while l < r (ensuring we don't use the same element twice):

   Calculate the sum s = nums[l] + nums[r] and compare with k:

   • Case 1: s == k - Found a valid pair!
     • Increment the answer: ans += 1
     • Move both pointers inward: l = l + 1 and r = r - 1
     • This removes both numbers from consideration
   • Case 2: s > k - Sum is too large
     • Move right pointer left: r -= 1
     • This decreases the sum by choosing a smaller right element
   • Case 3: s < k - Sum is too small
     • Move left pointer right: l += 1
     • This increases the sum by choosing a larger left element

4. Return result: After the loop ends (when l >= r), return ans as the maximum number of operations.

The algorithm efficiently finds all valid pairs in O(n log n) time due to sorting, with the two-pointer traversal taking only O(n) time. The space complexity is O(1) if we don't count the sorting space, as we only use a few variables to track positions and count.

This greedy approach guarantees the maximum number of operations because each valid pair found is immediately counted and removed, and the sorted order ensures we don't miss any possible pairs.

Example Walkthrough

Let's walk through a concrete example with nums = [3, 1, 3, 4, 3] and k = 6.

Step 1: Sort the array

• Original: [3, 1, 3, 4, 3]
• Sorted: [1, 3, 3, 3, 4]

Step 2: Initialize pointers and counter

• l = 0 (pointing to value 1)
• r = 4 (pointing to value 4)
• ans = 0

Step 3: Two-pointer traversal

Iteration 1:

• l = 0, r = 4: nums[0] + nums[4] = 1 + 4 = 5
• Sum (5) < k (6), so move left pointer right
• l = 1

Iteration 2:

• l = 1, r = 4: nums[1] + nums[4] = 3 + 4 = 7
• Sum (7) > k (6), so move right pointer left
• r = 3

Iteration 3:

• l = 1, r = 3: nums[1] + nums[3] = 3 + 3 = 6
• Sum equals k! Found a valid pair (3, 3)
• ans = 1, move both pointers: l = 2, r = 2

Iteration 4:

• l = 2, r = 2: Loop ends since l is not less than r

Step 4: Return result

• Maximum operations: ans = 1

The algorithm found one valid pair (3, 3) that sums to 6. Notice how the two-pointer approach efficiently navigated through the sorted array, adjusting pointers based on whether the current sum was too small, too large, or just right. The remaining element (3) at index 2 couldn't form a pair since all other elements were already used.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity is dominated by the sorting operation nums.sort(), which takes O(n × log n) time where n is the length of the input array nums. After sorting, the two-pointer traversal through the array takes O(n) time, as each element is visited at most once. Since O(n × log n) + O(n) = O(n × log n), the overall time complexity is O(n × log n).

Space Complexity: O(log n)

The space complexity is O(log n) due to the sorting algorithm. Python's built-in sort() method uses Timsort, which requires O(log n) space for the recursion stack in the worst case. The additional variables (l, r, ans, s) use only O(1) constant space. Therefore, the overall space complexity is O(log n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling Duplicate Elements Correctly

A common misconception is thinking that duplicate elements might cause issues or require special handling. However, the two-pointer approach naturally handles duplicates correctly.

Example scenario:

• nums = [1, 1, 2, 3, 3, 3], k = 4
• After sorting: [1, 1, 2, 3, 3, 3]
• The algorithm will correctly match (1, 3) twice, giving 2 operations

Why it works: Each element is used at most once because when we find a pair, we move both pointers inward, effectively "removing" those elements from future consideration.

2. Using a HashMap Instead When Two-Pointer is More Efficient

While a HashMap solution exists for this problem, some developers might default to it without considering the two-pointer approach:

HashMap approach (alternative but uses O(n) space):

def maxOperations(self, nums: List[int], k: int) -> int:
    count = {}
    operations = 0
  
    for num in nums:
        complement = k - num
        if complement in count and count[complement] > 0:
            operations += 1
            count[complement] -= 1
        else:
            count[num] = count.get(num, 0) + 1
  
    return operations

Trade-offs:

• HashMap: O(n) time, O(n) space, works on unsorted data
• Two-pointer: O(n log n) time, O(1) space (excluding sort), requires sorting

Choose two-pointer when you want to minimize space usage or when the array is already sorted.

3. Forgetting Edge Cases

Critical edge cases to consider:

• Empty array: nums = [] → should return 0
• Single element: nums = [5], k = 10 → should return 0 (need at least 2 elements for a pair)
• No valid pairs: nums = [1, 2, 3], k = 10 → should return 0
• All elements form pairs: nums = [1, 4, 2, 3], k = 5 → should return 2

4. Integer Overflow Concerns

In languages with fixed integer sizes, be careful about overflow when calculating nums[left] + nums[right]:

Potential issue:

# In languages like Java/C++, this could overflow:
int sum = nums[left] + nums[right];  // Could exceed INT_MAX

Solution in Python: Python handles arbitrary precision integers automatically, so overflow isn't a concern. In other languages, you might need to use long integers or check for overflow conditions.

5. Modifying the Original Array

The solution sorts the input array in-place with nums.sort(), which modifies the original array. If preserving the original array order is important:

Solution to preserve original:

def maxOperations(self, nums: List[int], k: int) -> int:
    # Create a copy before sorting
    nums_copy = nums.copy()  # or nums[:]
    nums_copy.sort()
  
    # Rest of the algorithm remains the same...
    left = 0
    right = len(nums_copy) - 1
    # ... continue with nums_copy

This adds O(n) space complexity but preserves the input array's original state.