Day 18 - Max Number of K-Sum Pairs
Tags: leetcode, python, challenge
Published: 2021-01-18 13:37:10

>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`

## Tests

[Link to code](https://github.com/ruarfff/leetcode-jan-2021)

```python
import pytest
from .Day18_MaxNumberOfKSumPairs import Solution

s = Solution()


@pytest.mark.parametrize(
    "nums,k,expected",
    [
        ([1, 2, 3, 4], 5, 2),
        ([3, 1, 3, 4, 3], 6, 1),
        ([3, 5, 1, 5], 2, 0),
        ([4, 4, 1, 3, 1, 3, 2, 2, 5, 5, 1, 5, 2, 1, 2, 3, 5, 4], 2, 2),
    ],
)
def test_max_operations(nums, k, expected):
    assert s.maxOperations(nums, k) == expected
```

## Solution

[Link to code](https://github.com/ruarfff/leetcode-jan-2021)

```python
from typing import List
import math


class Solution:
    def maxOperations(self, nums: List[int], k: int) -> int:
        max_ops = 0
        counts = {}
        for n in nums:
            if n in counts:
                counts[n] = counts[n] + 1
            else:
                counts[n] = 1

        for n in counts:
            diff = k - n
            if diff in counts and counts[diff] > 0:
                ops = 0
                if n == k // 2:
                    ops = math.floor(counts[n] // 2)
                else:
                    ops = min(counts[n], counts[diff])

                max_ops += ops
                counts[diff] = counts[diff] - ops
                counts[n] = counts[n] - ops

        return max_ops
```

## Analysis

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/oxj6akqc2l6x8mfz7yo4.png)

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/3wj6xja8k2wlv5fqg1mu.png)

## Commentary

A fairly easy and quick one today. I could definitely have improved it but it will do. 

Runtime is `O(n)`. We got over the list once to insert to a map. Then we go over the map keys and do our calculations. Space is `O(n)` because we created a map to store the counts. 

Using a map gives us a very quick way to look up `k - n` for each `n`. If we find a match, we can decrement the counts for each number in the match by `min(counts[n], counts[diff])` and increment the max operations by that number. 

The other case we need to think of is where `k - n` is `k / 2`. This will break our implementation so we need to add a check for that case and use `math.floor(counts[n] // 2)`. For example, take `k = 2` and `[1, 1, 1, 1]`. If we used `min(counts[n], counts[diff])` we'd get `4` but the correct answer would be `2` which we do get from `math.floor(counts[n] // 2)`.