Day 18 - Max Number of K-Sum Pairs

#leetcode #python #challenge

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

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

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

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).