#1679

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Max Number of K-Sum Pairs

Max Number of K-Sum Pairs is a problem involving counting disjoint pairs with a given sum k in an array.

Problem Statement

Given an integer array nums and an integer k, your task is to determine how many operations you can perform. In each operation, you must find two numbers in nums whose sum equals k, remove them, and continue until no more such pairs exist.

Return the maximum number of such operations. Each pair you remove must consist of disjoint elements, meaning once an element is used in a pair, it cannot be reused in another operation.

Examples

Example 1

Input: nums = [1,2,3,4], k = 5

Output: 2

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

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

Solution Approach

Hash Table Approach

First, initialize a hash table to count occurrences of each number in the array. Then, for each element in the array, check if its complement (k - num) exists in the hash table. If so, a pair can be formed, and both elements are removed from the hash table. This approach ensures we efficiently find pairs and avoid counting the same pair multiple times.

Greedy Pairing with Array Traversal

After populating the hash table, iterate through the array and greedily find pairs. For each number, attempt to match it with its complement. If both elements exist in the hash table, count it as a valid pair and reduce their respective counts. This ensures that each element is used only once in a pair.

Optimizing with Two Pointers

Sort the array, and then use a two-pointer technique to traverse the sorted array. One pointer starts at the beginning, and the other at the end. If the sum of the elements at the two pointers equals k, count it as a valid pair and move both pointers inward. If the sum is less than k, move the left pointer rightward, and if it is greater than k, move the right pointer leftward.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the final approach: Using a hash table results in O(n) time complexity, while sorting the array for the two-pointer approach brings it to O(n log n). Space complexity is O(n) due to the hash table storing counts of each element in nums.

What Interviewers Usually Probe

The candidate demonstrates knowledge of hash tables for efficiently pairing elements.
The candidate employs greedy algorithms or two-pointer techniques to find pairs in linear time.
The candidate shows understanding of time-space trade-offs when deciding between hash table and sorting approaches.

Common Pitfalls or Variants

Common pitfalls

Failing to check if elements are still available in the hash table before forming pairs can lead to overcounting.
Not handling edge cases like no pairs existing or repeated elements in the array.
Using inefficient approaches like brute force pair finding, which would result in O(n^2) time complexity.

Follow-up variants

Modify the problem to find k-sum pairs instead of pairs, expanding the problem to larger sums.
Change the problem so that you need to return the sum of the elements in the valid pairs.
Add constraints where the array contains duplicates, and elements can only be used once in all pairs.

FAQ

What is the approach to solving Max Number of K-Sum Pairs?

You can solve this problem using a hash table to store element counts or by applying the two-pointer technique after sorting the array.

What is the time complexity of the hash table approach?

The hash table approach runs in O(n) time, where n is the length of the array.

How do I avoid reusing elements in pairs?

By ensuring that once a pair is formed, both elements are removed or reduced in the hash table or array.

What if the array contains duplicates in Max Number of K-Sum Pairs?

Duplicates can still form valid pairs as long as they satisfy the sum condition, and each element can only be used once.

Can I use brute force to solve Max Number of K-Sum Pairs?

Brute force is not efficient and should be avoided because it leads to a time complexity of O(n^2). A hash table or two-pointer approach is much more efficient.

terminal

Solution

Solution 1: Sorting

We sort $nums$. Then $l$ and $r$ point to the first and last elements of $nums$ respectively, and we compare the sum $s$ of the two integers with $k$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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

Solution 2: Hash Table

We use a hash table $cnt$ to record the current remaining integers and their occurrence counts.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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

Continue Practicing

#1782 count pairs of nodes #1346 check if n and its double exist #1048 longest string chain