LeetCode Solutions Blog

Max Number of K-Sum Pairs

Number: 1798

Difficulty: Medium

Paid? No

Problem Description

Given an array of integers and an integer k, the task is to determine the maximum number of operations that can be performed where in each operation you remove two numbers that add up to k.

Key Insights

Use a hash table (or dictionary) to count frequency of each number.
For each number, determine if the complement (k - current number) exists.
Special handling is needed when the current number is exactly half of k, to avoid double counting.
An alternative approach is using sorting combined with two pointers, but the hash table method offers a clean O(n) solution.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

We use a hash table to keep track of how many times each number appears in the array. For each number, check if its complement (k - current value) exists in the hash table. If it does, increment the operation count and decrease the frequency of both the number and its complement. The special case arises when the number equals its complement, where we need to ensure there are at least two occurrences before making a pair. This approach allows us to solve the problem in a single pass through the array, achieving O(n) time complexity while using O(n) space for the hash table.

Code Solutions

# Python solution using dictionary for counting
class Solution:
    def maxOperations(self, nums: List[int], k: int) -> int:
        operations = 0  # count of valid operations
        count = {}  # dictionary to store frequency of each number
        
        # Count frequency of each number in the array
        for num in nums:
            count[num] = count.get(num, 0) + 1
        
        # Iterate through each unique number in the dictionary
        for num in list(count.keys()):
            complement = k - num  # calculate complement
            
            # If the complement exists in the dictionary
            if complement in count:
                # Special case: when num equals its complement, need at least 2 occurrences
                if num == complement:
                    pairs = count[num] // 2
                else:
                    # Number of pairs is limited by the frequency of the number and its complement
                    pairs = min(count[num], count[complement])
                
                operations += pairs  # increment operations by the number of pairs found
                # Update counts to zero to avoid reusing these numbers
                count[num] = 0
                count[complement] = 0
        
        return operations