Finding Pairs With a Certain Sum

Medium

Asked by:

+1

4 views

Topics:

Arrays

You are given two integer arrays nums1 and nums2. You are tasked to implement a data structure that supports queries of two types:

Add a positive integer to an element of a given index in the array nums2.
Count the number of pairs (i, j) such that nums1[i] + nums2[j] equals a given value (0 <= i < nums1.length and 0 <= j < nums2.length).

Implement the FindSumPairs class:

FindSumPairs(int[] nums1, int[] nums2) Initializes the FindSumPairs object with two integer arrays nums1 and nums2.
void add(int index, int val) Adds val to nums2[index], i.e., apply nums2[index] += val.
int count(int tot) Returns the number of pairs (i, j) such that nums1[i] + nums2[j] == tot.

Example 1:

Input
["FindSumPairs", "count", "add", "count", "count", "add", "add", "count"]
[[[1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]], [7], [3, 2], [8], [4], [0, 1], [1, 1], [7]]
Output
[null, 8, null, 2, 1, null, null, 11]

Explanation
FindSumPairs findSumPairs = new FindSumPairs([1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]);
findSumPairs.count(7);  // return 8; pairs (2,2), (3,2), (4,2), (2,4), (3,4), (4,4) make 2 + 5 and pairs (5,1), (5,5) make 3 + 4
findSumPairs.add(3, 2); // now nums2 = [1,4,5,4,5,4]
findSumPairs.count(8);  // return 2; pairs (5,2), (5,4) make 3 + 5
findSumPairs.count(4);  // return 1; pair (5,0) makes 3 + 1
findSumPairs.add(0, 1); // now nums2 = [2,4,5,4,5,4]
findSumPairs.add(1, 1); // now nums2 = [2,5,5,4,5,4]
findSumPairs.count(7);  // return 11; pairs (2,1), (2,2), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,4) make 2 + 5 and pairs (5,3), (5,5) make 3 + 4

Constraints:

1 <= nums1.length <= 1000
1 <= nums2.length <= 10⁵
1 <= nums1[i] <= 10⁹
1 <= nums2[i] <= 10⁵
0 <= index < nums2.length
1 <= val <= 10⁵
1 <= tot <= 10⁹
At most 1000 calls are made to add and count each.

Try coding it in LeetCode

Finding Pairs With a Certain Sum

Medium

Asked by:

4 views

Topics:

Arrays

You are given two integer arrays nums1 and nums2. You are tasked to implement a data structure that supports queries of two types:

Add a positive integer to an element of a given index in the array nums2.
Count the number of pairs (i, j) such that nums1[i] + nums2[j] equals a given value (0 <= i < nums1.length and 0 <= j < nums2.length).

Implement the FindSumPairs class:

FindSumPairs(int[] nums1, int[] nums2) Initializes the FindSumPairs object with two integer arrays nums1 and nums2.
void add(int index, int val) Adds val to nums2[index], i.e., apply nums2[index] += val.
int count(int tot) Returns the number of pairs (i, j) such that nums1[i] + nums2[j] == tot.

Example 1:

Input
["FindSumPairs", "count", "add", "count", "count", "add", "add", "count"]
[[[1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]], [7], [3, 2], [8], [4], [0, 1], [1, 1], [7]]
Output
[null, 8, null, 2, 1, null, null, 11]

Explanation
FindSumPairs findSumPairs = new FindSumPairs([1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]);
findSumPairs.count(7);  // return 8; pairs (2,2), (3,2), (4,2), (2,4), (3,4), (4,4) make 2 + 5 and pairs (5,1), (5,5) make 3 + 4
findSumPairs.add(3, 2); // now nums2 = [1,4,5,4,5,4]
findSumPairs.count(8);  // return 2; pairs (5,2), (5,4) make 3 + 5
findSumPairs.count(4);  // return 1; pair (5,0) makes 3 + 1
findSumPairs.add(0, 1); // now nums2 = [2,4,5,4,5,4]
findSumPairs.add(1, 1); // now nums2 = [2,5,5,4,5,4]
findSumPairs.count(7);  // return 11; pairs (2,1), (2,2), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,4) make 2 + 5 and pairs (5,3), (5,5) make 3 + 4

Constraints:

1 <= nums1.length <= 1000
1 <= nums2.length <= 10⁵
1 <= nums1[i] <= 10⁹
1 <= nums2[i] <= 10⁵
0 <= index < nums2.length
1 <= val <= 10⁵
1 <= tot <= 10⁹
At most 1000 calls are made to add and count each.

Try coding it in LeetCode

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 is the range of possible integer values within the input array?
Can the input array contain duplicate numbers, and if so, should I return all pairs that sum to the target, or just unique pairs?
If no pairs sum to the target, what should I return (e.g., null, an empty array, or throw an exception)?
Should I return the indices of the numbers that sum to the target, or the numbers themselves?
If multiple pairs sum to the target value, is there any preference as to which pair I should return? For example, should I return the first pair encountered, or prioritize pairs with smaller indices?

Brute Force Solution

Approach

We're given a list of numbers and a target sum. The brute force method checks every possible pairing of numbers to see if any pair adds up to the target.

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

Take the first number in the list.
Compare it with every other number in the list.
For each comparison, check if the sum of those two numbers equals the target sum.
If you find a pair that adds up correctly, remember it.
Now, move to the second number in the list.
Compare it with every number that comes after it in the list (you already compared it with the numbers before it).
Again, check if any of those pairs adds up to the target sum and remember any correct pairs.
Continue this process, going through each number in the list and comparing it with all the numbers that follow it.
At the end, you'll have a list of all the pairs that add up to the target sum.

Code Implementation

def find_pairs_with_certain_sum_brute_force(number_list, target_sum):
    found_pairs = []

    for first_number_index in range(len(number_list)):
        # Iterate through all possible pairs with the first number

        for second_number_index in range(first_number_index + 1, len(number_list)):
            # Avoid duplicate pairs by starting from the next index

            if number_list[first_number_index] + number_list[second_number_index] == target_sum:
                found_pairs.append((first_number_index, second_number_index))

    return found_pairs

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the input list of n numbers. For each number, it compares it with the remaining numbers in the list to find a pair that sums to the target. In the worst-case scenario, for each of the n numbers, we iterate through approximately n numbers. Therefore, the total number of comparisons is proportional to n * n, resulting in a time complexity of O(n²).

Space Complexity

O(P) – The algorithm, as described, remembers the pairs that sum to the target. In the worst-case scenario, every possible pair could sum to the target. If P is the number of pairs that sum to the target, we need to store P pairs. Therefore, the space used is proportional to the number of pairs found, P, leading to a space complexity of O(P).

Optimal Solution

Approach

To efficiently find pairs that add up to a target number, we use a method that quickly checks if the number needed to complete the pair exists. This way, we avoid comparing each number with every other number, saving a lot of time.

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

Think of having a way to remember each number you've seen so far.
Go through the numbers one by one.
For each number, figure out what other number would be needed to reach the target sum.
Check if you've already seen that needed number before using your memory of past numbers.
If you have, then you've found a pair that adds up to the target. Hooray!
If you haven't, remember this number for later, so you can check against it as you go through the rest of the list.
Continue this until you've looked at all the numbers.

Code Implementation

def find_pairs_with_sum(number_list, target_sum):
    seen_numbers = set()
    pairs = []

    for current_number in number_list:
        complement = target_sum - current_number

        # Check if the complement exists in the numbers we've seen so far.
        if complement in seen_numbers:
            pairs.append((current_number, complement))

        # Store the current number to check against later complements.
        seen_numbers.add(current_number)

    return pairs

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n once. For each element, it performs a constant-time operation to calculate the complement and checks if the complement exists in a hash set (or dictionary), which also takes constant time on average. Therefore, the time complexity is dominated by the single loop that iterates through all n elements. Thus, the overall time complexity is O(n).

Space Complexity

O(N) – The provided solution description uses a data structure (implied to be a hash set or similar) to remember each number seen so far. In the worst-case scenario, where no pairs sum to the target until the very end or not at all, this data structure might store all N numbers from the input. Therefore, the auxiliary space required grows linearly with the input size N, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or undefined input array	Throw an IllegalArgumentException or return an empty list immediately.
Array with only one element	Return an empty list immediately since a pair requires at least two elements.
Large input array size that could cause memory issues with a hashmap approach	Consider using a two-pointer approach after sorting if memory is a constraint, though it would change time complexity.
Array contains extremely large positive or negative numbers that could lead to integer overflow when summing	Use long data type to prevent integer overflow during the summation.
Target sum is very large or very small compared to the array elements	The algorithm should still correctly identify (or not identify) matching pairs regardless of the target's magnitude.
No pairs exist that sum to the target value	Return an empty list when no such pairs are found, indicating no solution.
Multiple pairs exist that sum to the target value, and the prompt only asks for one pair	Return the first pair found or all pairs if the problem asks for all.
Array contains duplicate pairs of numbers summing to target	Store the pairs in a set to avoid duplicate pairs in the results, if necessary.