Solution Explanation for Max Number of K-Sum Pairs

The problem asks to find the maximum number of pairs in an integer array nums that sum up to a given integer k. We can solve this efficiently using two approaches: sorting and using a hash table.

Approach 1: Sorting + Two Pointers

This approach leverages the efficiency of binary search implicitly through two pointers.

1. Sort the array: First, we sort the input array nums in ascending order. This step allows us to efficiently find pairs that sum to k. Sorting takes O(n log n) time.

2. Two Pointers: We use two pointers, l and r, initialized to the beginning and end of the sorted array, respectively.

3. Iteration: The core logic lies in the while loop:

   • We calculate the sum s = nums[l] + nums[r].
   • Case 1 (s == k): If the sum equals k, we've found a pair. We increment the ans (our counter for successful pairs), move l one step to the right, and r one step to the left.
   • Case 2 (s > k): If the sum is greater than k, we need a smaller sum, so we decrement r (move to a smaller number).
   • Case 3 (s < k): If the sum is less than k, we need a larger sum, so we increment l (move to a larger number).
   • The loop continues until l and r cross each other (l >= r), indicating we've checked all possible pairs.

4. Return ans: Finally, we return the total count of pairs found, ans.

Time Complexity: O(n log n) due to sorting. The two-pointer iteration is O(n). Space Complexity: O(log n) or O(1) depending on the sorting algorithm used (in-place sorting algorithms like merge sort have O(log n) space complexity due to recursion; some implementations might have O(1) in-place).

Approach 2: Hash Table

This approach uses a hash table (or dictionary/map) to store the frequency of each number in the array.

1. Frequency Count: We iterate through nums and store the frequency of each number in a hash table cnt. This takes O(n) time.

2. Pair Check: For each number x in nums, we check if k - x exists in cnt.

   • Found: If k - x exists, we have found a pair. We increment ans and decrement the frequency of k - x in cnt. This ensures we don't reuse the same number in multiple pairs.
   • Not Found: If k - x doesn't exist, we simply increment the frequency of x in cnt.

3. Return ans: After iterating through all numbers, we return ans.

Time Complexity: O(n) because both iterating through nums and checking the hash table take linear time. Space Complexity: O(n) in the worst case to store the frequency of all numbers in the hash table.

Code Examples (Python)

Approach 1 (Sorting):

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

Approach 2 (Hash Table):

from collections import Counter
 
class Solution:
    def maxOperations(self, nums: List[int], k: int) -> int:
        cnt = Counter(nums)
        ans = 0
        for x in nums:
            if cnt[k - x] > 0:
                ans += 1
                cnt[k - x] -= 1
                if cnt[x] > 0 :
                    cnt[x] -= 1
        return ans

Both approaches correctly solve the problem. The choice depends on the specific constraints and performance requirements. If memory is a major concern and n is very large, the sorting approach might be preferred because while it's O(n log n), the constant factor might be smaller than the hash table approach's O(n) with its higher constant factors depending on the hash table implementation. Otherwise, the hash table approach is generally faster due to its linear time complexity.