Jobs

Interviews

Discussions

Max Number of K-Sum Pairs

Medium

DE Shaw

4 views

Topics:

ArraysTwo Pointers

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.

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.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
1 <= k <= 10⁹

Max Number of K-Sum Pairs

Medium

DE Shaw

4 views

Topics:

ArraysTwo Pointers

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.

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.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
1 <= k <= 10⁹

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the input array `nums` and the range of values within `nums` and for `k`?
Can the array `nums` contain negative numbers, zeros, or only positive integers?
If no two numbers in `nums` sum up to `k`, should I return 0?
Are we guaranteed that `k` will always be a valid integer?
If there are multiple pairs that sum up to k, should I find the *maximum* number of such pairs, and does order matter (e.g., can I reuse a number after its initial pairing)?

Brute Force Solution

Approach

We need to find pairs of numbers from a collection that add up to a specific target number. The brute force method is simple: we'll just check every possible pair to see if it meets the criteria.

Here's how the algorithm would work step-by-step:

Take the first number in the collection.
Pair it with every other number in the collection, one at a time.
For each pair, add the two numbers together.
If the sum equals the target number, we've found a valid pair, so increase our count of valid pairs.
Once we've paired the first number with every other number, move on to the second number in the collection.
Pair the second number with every number after it in the collection (to avoid counting the same pair twice).
Repeat the process of summing and checking against the target until we've considered all possible pairs.
The final count represents the maximum number of pairs that sum to the target.

Code Implementation

def max_number_of_k_sum_pairs_brute_force(numbers, target):
    number_of_pairs = 0

    # Iterate through each number in the list.
    for first_number_index in range(len(numbers)):

        # To avoid double counting, we only check pairs after the current index
        for second_number_index in range(first_number_index + 1, len(numbers)):
            if numbers[first_number_index] + numbers[second_number_index] == target:
                number_of_pairs += 1

    # Return the total number of k-sum pairs.
    return number_of_pairs

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The brute force approach iterates through each element of the input array of size n. For each element, it then iterates through the rest of the array to find a pair that sums up to the target value. This nested iteration results in roughly n * (n-1) / 2 comparisons. Therefore, the time complexity can be approximated as O(n²).

Space Complexity

O(1) – The described brute force approach iterates through pairs within the input collection. It uses a constant number of variables, such as indices and a count for the pairs found. No auxiliary data structures that scale with the input size N are used to store intermediate results or track visited elements. Therefore, the space complexity remains constant, independent of the number of elements in the input collection.

Optimal Solution

Approach

The best way to solve this problem is to efficiently find pairs that add up to the target number. We can do this by looking at the numbers one by one and quickly checking if their 'partner' exists.

Here's how the algorithm would work step-by-step:

First, count how many times each number appears in the given set of numbers.
Then, go through each unique number in the set.
For each number, see if its 'partner' (the number that adds up to the target when combined with the current number) is also in the set.
If the 'partner' exists, determine how many pairs you can make using the number of times each number appears (you might have fewer of one or the other).
Count the number of pairs you create and reduce the counts of each number accordingly.
By systematically checking each number and its partner, we avoid redundant comparisons and find the maximum number of pairs quickly.

Code Implementation

def max_number_of_k_sum_pairs(numbers, target):
    number_counts = {}
    for number in numbers:
        number_counts[number] = number_counts.get(number, 0) + 1

    number_of_pairs = 0

    for number in list(number_counts.keys()):
        complement = target - number

        # Only proceed if the complement exists
        if complement in number_counts:

            # Need to handle the case where the number and complement are the same
            if number == complement:
                pairs_formed = number_counts[number] // 2
                number_of_pairs += pairs_formed
                number_counts[number] -= pairs_formed * 2

            # Handle cases where the number and complement are distinct
            else:
                pairs_formed = min(number_counts[number], number_counts[complement])

                # Update pair counts and remove used numbers
                number_of_pairs += pairs_formed
                number_counts[number] -= pairs_formed
                number_counts[complement] -= pairs_formed
    
    return number_of_pairs

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – First, we iterate through the input array of n elements to count the frequency of each number using a hash map, which takes O(n) time. Then, we iterate through the unique numbers in the hash map, which is at most n. During this iteration, we check if the 'partner' exists in the hash map, which takes O(1) time. Therefore, the second loop takes O(n) time. Thus, the overall time complexity is dominated by the initial frequency count and checking for pairs, both of which take linear time, resulting in O(n) complexity.

Space Complexity

O(N) – The provided solution uses a dictionary (or hash map) to count the frequency of each number in the input array. In the worst case, all N numbers in the input array are unique, resulting in a dictionary storing N key-value pairs. Therefore, the auxiliary space required to store the frequency counts scales linearly with the size of the input array N, leading to a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty input array	Return 0 immediately, as no operations are possible.
Input array with only one element	Return 0, as a pair requires at least two elements.
k is zero and array contains zero(s)	Handle zero pairs correctly; the count of zeros must be considered carefully to avoid overcounting.
All numbers in the array are the same, and sum equals k	Properly count pairs; Divide the count of the number by 2.
k is negative, array has positive, negative, and zero values	The solution should correctly handle negative numbers contributing to the sum k.
Large input array, nearing memory limit	Use an efficient data structure (e.g., hash map or frequency counter) to avoid exceeding memory constraints.
Input array contains Integer.MAX_VALUE or Integer.MIN_VALUE, potentially leading to integer overflow when summing with k	Use a data type that can handle larger values (e.g., long) or carefully check for potential overflows before performing arithmetic operations.
No pairs in array sum to k	Return 0, as no operations are possible when no suitable pairs are present.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the input array `nums` and the range of values within `nums` and for `k`?
Can the array `nums` contain negative numbers, zeros, or only positive integers?
If no two numbers in `nums` sum up to `k`, should I return 0?
Are we guaranteed that `k` will always be a valid integer?
If there are multiple pairs that sum up to k, should I find the *maximum* number of such pairs, and does order matter (e.g., can I reuse a number after its initial pairing)?

Brute Force Solution

Approach

We need to find pairs of numbers from a collection that add up to a specific target number. The brute force method is simple: we'll just check every possible pair to see if it meets the criteria.

Here's how the algorithm would work step-by-step:

Take the first number in the collection.
Pair it with every other number in the collection, one at a time.
For each pair, add the two numbers together.
If the sum equals the target number, we've found a valid pair, so increase our count of valid pairs.
Once we've paired the first number with every other number, move on to the second number in the collection.
Pair the second number with every number after it in the collection (to avoid counting the same pair twice).
Repeat the process of summing and checking against the target until we've considered all possible pairs.
The final count represents the maximum number of pairs that sum to the target.

Code Implementation

def max_number_of_k_sum_pairs_brute_force(numbers, target):
    number_of_pairs = 0

    # Iterate through each number in the list.
    for first_number_index in range(len(numbers)):

        # To avoid double counting, we only check pairs after the current index
        for second_number_index in range(first_number_index + 1, len(numbers)):
            if numbers[first_number_index] + numbers[second_number_index] == target:
                number_of_pairs += 1

    # Return the total number of k-sum pairs.
    return number_of_pairs

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The best way to solve this problem is to efficiently find pairs that add up to the target number. We can do this by looking at the numbers one by one and quickly checking if their 'partner' exists.

Here's how the algorithm would work step-by-step:

First, count how many times each number appears in the given set of numbers.
Then, go through each unique number in the set.
For each number, see if its 'partner' (the number that adds up to the target when combined with the current number) is also in the set.
If the 'partner' exists, determine how many pairs you can make using the number of times each number appears (you might have fewer of one or the other).
Count the number of pairs you create and reduce the counts of each number accordingly.
By systematically checking each number and its partner, we avoid redundant comparisons and find the maximum number of pairs quickly.

Code Implementation

def max_number_of_k_sum_pairs(numbers, target):
    number_counts = {}
    for number in numbers:
        number_counts[number] = number_counts.get(number, 0) + 1

    number_of_pairs = 0

    for number in list(number_counts.keys()):
        complement = target - number

        # Only proceed if the complement exists
        if complement in number_counts:

            # Need to handle the case where the number and complement are the same
            if number == complement:
                pairs_formed = number_counts[number] // 2
                number_of_pairs += pairs_formed
                number_counts[number] -= pairs_formed * 2

            # Handle cases where the number and complement are distinct
            else:
                pairs_formed = min(number_counts[number], number_counts[complement])

                # Update pair counts and remove used numbers
                number_of_pairs += pairs_formed
                number_counts[number] -= pairs_formed
                number_counts[complement] -= pairs_formed
    
    return number_of_pairs

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0 immediately, as no operations are possible.
Input array with only one element	Return 0, as a pair requires at least two elements.
k is zero and array contains zero(s)	Handle zero pairs correctly; the count of zeros must be considered carefully to avoid overcounting.
All numbers in the array are the same, and sum equals k	Properly count pairs; Divide the count of the number by 2.
k is negative, array has positive, negative, and zero values	The solution should correctly handle negative numbers contributing to the sum k.
Large input array, nearing memory limit	Use an efficient data structure (e.g., hash map or frequency counter) to avoid exceeding memory constraints.
Input array contains Integer.MAX_VALUE or Integer.MIN_VALUE, potentially leading to integer overflow when summing with k	Use a data type that can handle larger values (e.g., long) or carefully check for potential overflows before performing arithmetic operations.
No pairs in array sum to k	Return 0, as no operations are possible when no suitable pairs are present.