# Max Number of K-Sum Pairs
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/max-number-of-k-sum-pairs)
Canonical: https://scaleengineer.com/dsa/problems/max-number-of-k-sum-pairs
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
**Companies:** [DE Shaw](https://scaleengineer.com/companies/de-shaw)
---
## Problem
You are given an integer array `nums` and an integer `k`.

In one operation, you can pick two numbers from the array whose sum equals `k` and remove them from the array.

Return _the maximum number of operations you can perform on the array_.

**Example 1:**

**Input:** nums = [1,2,3,4], k = 5
**Output:** 2
**Explanation:** Starting with nums = [1,2,3,4]:
- Remove numbers 1 and 4, then nums = [2,3]
- Remove numbers 2 and 3, then nums = []
There are no more pairs that sum up to 5, hence a total of 2 operations.

**Example 2:**

**Input:** nums = [3,1,3,4,3], k = 6
**Output:** 1
**Explanation:** Starting with nums = [3,1,3,4,3]:
- Remove the first two 3's, then nums = [1,4,3]
There are no more pairs that sum up to 6, hence a total of 1 operation.

**Constraints:**

* `1 <= nums.length <= 105`
* `1 <= nums[i] <= 109`
* `1 <= k <= 109`

# Approaches
## Brute Force with Nested Loops
This approach uses a brute-force method to find all possible pairs. It involves iterating through the array with two nested loops to check every unique pair of numbers. To prevent using the same number in multiple pairs, a boolean array is used to mark numbers that have been included in a pair.
**Time:** O(n^2), where n is the number of elements in the array. The nested loops result in a quadratic number of comparisons in the worst case. · **Space:** O(n), where n is the number of elements in the array. This space is used for the `used` boolean array to track which elements have been paired.
**Pros:** Simple to understand and implement.; Works correctly for small input sizes.
**Cons:** Extremely inefficient for large arrays, likely resulting in a 'Time Limit Exceeded' error on competitive programming platforms.
### Explanation
The core idea is to examine every possible pair of elements `(nums[i], nums[j])` in the array. We use a primary loop to pick the first element `nums[i]` and a nested loop to pick the second element `nums[j]`, ensuring `j > i` to avoid duplicate pairs and self-pairing.

To handle the constraint that each number can only be used once, we maintain a boolean array `used` of the same size as `nums`. When we find a pair `(nums[i], nums[j])` that sums to `k`, and neither element has been used before (i.e., `used[i]` and `used[j]` are both `false`), we increment our operation count and set both `used[i]` and `used[j]` to `true`. We then break the inner loop for the current `i` because `nums[i]` is now part of a pair and cannot be used again.

```java
import java.util.Arrays;

class Solution {
    public int maxOperations(int[] nums, int k) {
        int operations = 0;
        int n = nums.length;
        boolean[] used = new boolean[n];
        
        for (int i = 0; i < n; i++) {
            if (used[i]) {
                continue;
            }
            for (int j = i + 1; j < n; j++) {
                if (used[j]) {
                    continue;
                }
                if (nums[i] + nums[j] == k) {
                    operations++;
                    used[i] = true;
                    used[j] = true;
                    break; // Move to the next i since nums[i] is now used
                }
            }
        }
        return operations;
    }
}
```
### Algorithm
*   Initialize `operations` to 0.
*   Create a boolean array `used` of the same size as `nums`, and initialize all its values to `false`.
*   Iterate through the `nums` array with an index `i` from `0` to `n-1`.
*   If `used[i]` is `true`, it means the number has already been paired, so we `continue` to the next element.
*   Inside the first loop, start a second, nested loop with an index `j` from `i + 1` to `n-1`.
*   If `used[j]` is `true`, `continue` to the next element.
*   Check if `nums[i] + nums[j] == k`.
*   If the sum is equal to `k`, we have found a pair. Increment `operations`, set `used[i]` and `used[j]` to `true`, and `break` from the inner loop since `nums[i]` has now been used.
*   After the loops complete, return the total `operations` count.

## Sorting with Two Pointers
A significantly better approach is to first sort the array. Once sorted, we can use the two-pointer technique. We place one pointer at the beginning of the array and another at the end. By comparing the sum of the values at these pointers with `k`, we can efficiently find pairs by moving the pointers inward.
**Time:** O(n log n), dominated by the initial sorting of the array. The subsequent two-pointer scan takes only O(n) time. · **Space:** O(log n) or O(n), depending on the implementation of the sorting algorithm. In Java, `Arrays.sort()` for primitive types has an average space complexity of O(log n).
**Pros:** Much more efficient than the brute-force approach.; Space-efficient, as it can be done with O(log n) or O(1) extra space depending on the sort implementation and if in-place sorting is allowed.
**Cons:** The time complexity is dominated by the sorting step, making it less efficient than the hash map approach.; Modifies the input array by sorting it, which might not be permissible in all contexts. A copy would require O(n) space.
### Explanation
This method leverages the fact that if the array is sorted, we can make intelligent decisions about which elements to pair. After sorting `nums`, we set up a `left` pointer at index 0 and a `right` pointer at the last index.

We then check the sum `nums[left] + nums[right]`. 
- If the sum equals `k`, we've found a valid pair. We count this operation and move both pointers inward (`left++`, `right--`) to search for other potential pairs.
- If the sum is less than `k`, we need a larger value to reach the target `k`. Since the array is sorted, we move the `left` pointer to the right to include a larger number in the sum.
- If the sum is greater than `k`, we need a smaller value. We move the `right` pointer to the left to include a smaller number.

This process continues until the pointers cross (`left >= right`), at which point we have found all possible pairs.

```java
import java.util.Arrays;

class Solution {
    public int maxOperations(int[] nums, int k) {
        Arrays.sort(nums);
        int left = 0;
        int right = nums.length - 1;
        int operations = 0;
        
        while (left < right) {
            int currentSum = nums[left] + nums[right];
            if (currentSum == k) {
                operations++;
                left++;
                right--;
            } else if (currentSum < k) {
                left++;
            } else { // currentSum > k
                right--;
            }
        }
        return operations;
    }
}
```
### Algorithm
*   Sort the input array `nums` in non-decreasing order.
*   Initialize an integer `operations` to 0.
*   Initialize two pointers: `left` at the start of the array (index 0) and `right` at the end of the array (index `n-1`).
*   Loop while `left` is less than `right`.
*   Calculate the sum of the elements at the two pointers: `sum = nums[left] + nums[right]`.
*   If `sum == k`, a pair is found. Increment `operations`, move the left pointer one step to the right (`left++`), and move the right pointer one step to the left (`right--`).
*   If `sum < k`, the sum is too small. To increase it, move the `left` pointer one step to the right (`left++`).
*   If `sum > k`, the sum is too large. To decrease it, move the `right` pointer one step to the left (`right--`).
*   The loop terminates when `left` and `right` pointers meet or cross. Return the final `operations` count.

## Using a Hash Map (Frequency Counter)
The most time-efficient solution uses a hash map to act as a frequency counter. By iterating through the array once, we can check for the existence of a complementary number (`k - num`) in constant time on average. This avoids the need for sorting or nested loops.
**Time:** O(n), where n is the number of elements in the array. This is because we iterate through the array once, and hash map operations (put and get) take, on average, O(1) time. · **Space:** O(n) in the worst case. If all elements in `nums` are distinct and no pairs are formed, the hash map will store up to `n` entries.
**Pros:** Optimal time complexity of O(n).; Processes the array in a single pass.
**Cons:** Requires extra space to store the frequency map, which can be up to O(n) in the worst case.
### Explanation
This approach provides a linear time solution by using a hash map to keep track of the frequencies of numbers we have encountered. We iterate through the `nums` array just once.

For each number `num`, we calculate the `complement` we need to form a sum of `k` (i.e., `complement = k - num`). We then look in our `frequencyMap` for this `complement`.

- If the `complement` is in the map and its count is positive, it means we have a previously seen number that can form a pair with the current `num`. We increment our `operations` count and decrement the count of the `complement` in the map to signify it has been used.
- If the `complement` is not in the map or its count is zero, we cannot form a pair at this moment. Instead, we add the current `num` to the map (or increment its count if it's already there), making it available for future numbers to pair with.

This single-pass strategy ensures that every number is processed efficiently to find its partner.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int maxOperations(int[] nums, int k) {
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        int operations = 0;
        
        for (int num : nums) {
            int complement = k - num;
            if (frequencyMap.getOrDefault(complement, 0) > 0) {
                // Found a pair, use the complement
                operations++;
                frequencyMap.put(complement, frequencyMap.get(complement) - 1);
            } else {
                // No pair found, store the current number for future matches
                frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
            }
        }
        return operations;
    }
}
```
### Algorithm
*   Initialize `operations` to 0 and create an empty hash map, `frequencyMap`, to store number frequencies.
*   Iterate through each `num` in the `nums` array.
*   For each `num`, calculate its required complement: `complement = k - num`.
*   Check if the `complement` exists as a key in `frequencyMap` and has a value (frequency) greater than 0.
*   If it does, a pair is found. Increment `operations` and decrement the frequency of the `complement` in the map.
*   If the `complement` is not found or its frequency is 0, it means we haven't found a match for the current `num` yet. Store the current `num` in the map by incrementing its frequency count.
*   After iterating through all numbers, return the total `operations` count.

# Solutions
### Java

```java
class Solution {
public
  int maxOperations(int[] nums, int k) {
    Arrays.sort(nums);
    int l = 0, r = nums.length - 1;
    int ans = 0;
    while (l < r) {
      int s = nums[l] + nums[r];
      if (s == k) {
        ++ans;
        ++l;
        --r;
      } else if (s > k) {
        --r;
      } else {
        ++l;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxOperations(vector<int> &nums, int k) {
    sort(nums.begin(), nums.end());
    int cnt = 0;
    int i = 0, j = nums.size() - 1;
    while (i < j) {
      if (nums[i] + nums[j] == k) {
        i++;
        j--;
        cnt++;
      } else if (nums[i] + nums[j] > k) {
        j--;
      } else {
        i++;
      }
    }
    return cnt;
  }
};

```

### Python

```python
class Solution:
    def maxOperations(self, nums: List[int], k: int) -> int: nums . sort() l, r, ans = 0, len(nums) - 1, 0 while l < r: s = nums[l] + nums[r] if s == k: ans += 1 l, r = l + 1, r - 1 elif s > k: r -= 1 else: l += 1 return ans

```