Taro Logo

Max Number of K-Sum Pairs

Medium
Google logo
Google
2 views
Topics:
ArraysTwo PointersGreedy Algorithms

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.

For example:

  1. If nums = [1,2,3,4] and k = 5, the answer is 2. We remove 1 and 4, then 2 and 3.
  2. If nums = [3,1,3,4,3] and k = 6, the answer is 1. We remove two 3s.

Constraints:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= 10^9

How would you approach solving this problem efficiently?

Solution


Naive Solution

A brute force solution would involve iterating through all possible pairs in the array and checking if their sum equals k. If a pair is found, increment the operation count and remove those elements from the array. This process repeats until no such pairs are found.

Pseudocode

function maxOperationsBruteForce(nums, k):
  count = 0
  while True:
    found = False
    for i from 0 to nums.length - 1:
      for j from i + 1 to nums.length - 1:
        if nums[i] + nums[j] == k:
          remove nums[j]  // Remove the larger index first to avoid shifting issues
          remove nums[i]
          count = count + 1
          found = True
          break  // Restart the outer loop after removing elements
      if found:
        break
    if not found:
      return count

Complexity Analysis

  • Time Complexity: O(n^2 * (n + n)), where n is the length of the array. The nested loops iterate through all possible pairs O(n^2), and removing elements from the list takes O(n) in each loop because the list needs to be re-indexed after the removal. Therefore, time complexity is O(n^3).
  • Space Complexity: O(1). The brute force approach modifies the input list in place and uses a constant amount of extra space.

Optimal Solution: Using a Hash Map

A more efficient solution involves using a hash map to store the frequency of each number in the array. Iterate through the array, and for each number num, check if k - num exists in the hash map. If it does, decrement the frequency of both num and k - num in the hash map (or remove them if the frequency becomes zero) and increment the operation count. If k - num does not exist, add num to the hash map (or increment its frequency if it already exists).

Pseudocode

function maxOperationsOptimal(nums, k):
  count = 0
  freqMap = {}

  for num in nums:
    complement = k - num
    if complement in freqMap and freqMap[complement] > 0:
      count = count + 1
      freqMap[complement] = freqMap[complement] - 1
      if freqMap[complement] == 0:
          remove complement from freqMap
    else:
      if num in freqMap:
        freqMap[num] = freqMap[num] + 1
      else:
        freqMap[num] = 1

  return count

Code (Python)

from collections import Counter

def maxOperations(nums, k):
    count = 0
    freq = Counter(nums)
    
    for num in nums:
        if freq[num] > 0:
            complement = k - num
            if complement in freq and freq[complement] > 0:
                if num == complement and freq[num] < 2:
                    continue
                count += 1
                freq[num] -= 1
                freq[complement] -= 1
    return count

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the array. We iterate through the array once.
  • Space Complexity: O(n) in the worst case, where n is the length of the array. This is because, in the worst-case scenario, all the elements in the array can be unique, and each element needs to be stored in the hash map.

Edge Cases

  • Empty Array: If the input array is empty, the function should return 0.
  • No pairs sum to k: If no pairs in the array sum up to k, the function should return 0.
  • Duplicate numbers: The hash map correctly handles scenarios with duplicate numbers in the array.
  • k is even, and two identical numbers must be used: Special handling might be needed in the case that num == k - num. We need to ensure that there are at least two of these numbers.