DEV Community

loading...

Day 18 - Max Number of K-Sum Pairs

ruarfff profile image Ruairí O'Brien ・2 min read

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.
Enter fullscreen mode Exit fullscreen mode

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.
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Analysis

Alt Text

Alt Text

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

Discussion (0)

pic
Editor guide