Jobs

Interviews

Discussions

3Sum With Multiplicity

Medium

Quora

3 views

Topics:

ArraysTwo Pointers

Given an integer array arr, and an integer target, return the number of tuples i, j, k such that i < j < k and arr[i] + arr[j] + arr[k] == target.

As the answer can be very large, return it modulo 10⁹ + 7.

Example 1:

Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20
Explanation: 
Enumerating by the values (arr[i], arr[j], arr[k]):
(1, 2, 5) occurs 8 times;
(1, 3, 4) occurs 8 times;
(2, 2, 4) occurs 2 times;
(2, 3, 3) occurs 2 times.

Example 2:

Input: arr = [1,1,2,2,2,2], target = 5
Output: 12
Explanation: 
arr[i] = 1, arr[j] = arr[k] = 2 occurs 12 times:
We choose one 1 from [1,1] in 2 ways,
and two 2s from [2,2,2,2] in 6 ways.

Example 3:

Input: arr = [2,1,3], target = 6
Output: 1
Explanation: (1, 2, 3) occured one time in the array so we return 1.

Constraints:

3 <= arr.length <= 3000
0 <= arr[i] <= 100
0 <= target <= 300

Try coding it in LeetCode

3Sum With Multiplicity

Medium

Quora

3 views

Topics:

ArraysTwo Pointers

Given an integer array arr, and an integer target, return the number of tuples i, j, k such that i < j < k and arr[i] + arr[j] + arr[k] == target.

As the answer can be very large, return it modulo 10⁹ + 7.

Example 1:

Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20
Explanation: 
Enumerating by the values (arr[i], arr[j], arr[k]):
(1, 2, 5) occurs 8 times;
(1, 3, 4) occurs 8 times;
(2, 2, 4) occurs 2 times;
(2, 3, 3) occurs 2 times.

Example 2:

Input: arr = [1,1,2,2,2,2], target = 5
Output: 12
Explanation: 
arr[i] = 1, arr[j] = arr[k] = 2 occurs 12 times:
We choose one 1 from [1,1] in 2 ways,
and two 2s from [2,2,2,2] in 6 ways.

Example 3:

Input: arr = [2,1,3], target = 6
Output: 1
Explanation: (1, 2, 3) occured one time in the array so we return 1.

Constraints:

3 <= arr.length <= 3000
0 <= arr[i] <= 100
0 <= target <= 300

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 values within the input array `arr`? Could there be negative numbers, zeros, or very large positive numbers?
What is the maximum size of the input array `arr`? This will help me consider potential time complexity constraints.
If there are multiple triplets that sum to `target`, should I return all of them, and if so, how should the result be formatted (e.g., a list of tuples, a list of lists)?
Is the order of elements within each triplet important? Should the triplets themselves be returned in a specific order?
If no triplets sum up to the target, what should I return (e.g., an empty list, null, or a specific error code)?

Brute Force Solution

Approach

The goal is to find groups of three numbers that add up to a specific target. The brute force approach simply tries every possible combination of three numbers from the given set.

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

Consider the first number in the set.
Pair that number with the second number in the set.
Now, for that pair, consider every other number in the set and see if the three numbers add up to the target.
If they do, count that combination.
If they don't, move to the next number.
Repeat steps 2-5 for every number in the set after the first number.
Repeat steps 1-6 for every number in the set.

Code Implementation

def three_sum_brute_force(numbers, target):    count = 0
    array_length = len(numbers)

    for first_number_index in range(array_length):

        for second_number_index in range(first_number_index + 1, array_length):
            # Ensures we don't repeat pairs by only considering later indices

            for third_number_index in range(second_number_index + 1, array_length):
                # Prevents duplicate triplets.

                if numbers[first_number_index] + numbers[second_number_index] + numbers[third_number_index] == target:
                    # Increment the count when a valid triplet is found.
                    count += 1

    return count

Big(O) Analysis

Time Complexity

O(n^3) – The algorithm iterates through the array using three nested loops. The outermost loop considers each element as the first number of the triplet. The second loop considers each element after the current first element as the second number of the triplet. The innermost loop considers each element after the second number as the third number of the triplet to check if their sum equals the target. Therefore, the number of operations is proportional to n * n * n, resulting in a time complexity of O(n^3).

Space Complexity

O(1) – The provided plain English solution describes a brute-force approach to the 3Sum problem with multiplicity. It involves nested loops iterating through the input array without using any auxiliary data structures like hash maps, lists, or sets. No significant extra space is allocated beyond a few loop index variables. Therefore, the space complexity is constant, independent of the input array size N.

Optimal Solution

Approach

The efficient solution avoids checking every possible combination. It counts the frequency of each number to quickly calculate how many valid triplets exist, significantly reducing the computation needed.

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

First, count how many times each number appears in the list.
Then, consider all possible combinations of three numbers from the list, allowing for duplicates.
For each combination, check if their sum equals the target number.
If the sum is correct, calculate how many triplets of that exact combination exist based on the frequency counts of each number in that combination.
If the three numbers are all different, multiply their individual counts.
If two numbers are the same, use a combination formula to find the number of pairs you can form using the frequency count.
If all three numbers are the same, use a different combination formula to calculate the number of triplets.
Add up the number of triplets for all combinations that sum to the target. Make sure to apply modulo to the final answer to avoid overflow.

Code Implementation

from collections import Counter

def three_sum_multiplicity(array, target):
    frequency = Counter(array)
    keys = sorted(frequency.keys())
    mod = 10**9 + 7
    answer = 0

    for i in range(len(keys)):
        first_number = keys[i]
        for j in range(i, len(keys)):
            second_number = keys[j]
            third_number_needed = target - first_number - second_number

            if third_number_needed in frequency and third_number_needed >= second_number:
                third_number = third_number_needed
                frequency_first = frequency[first_number]
                frequency_second = frequency[second_number]
                frequency_third = frequency[third_number]

                # All 3 numbers are the same
                if first_number == second_number == third_number:
                    # Use combinations formula nCr = n! / (r! * (n-r)!) where r = 3
                    answer += (frequency_first * (frequency_first - 1) * (frequency_first - 2) // 6)

                # Only the first and second numbers are the same
                elif first_number == second_number:
                    # Use combinations formula nCr = n! / (r! * (n-r)!) where r = 2
                    answer += (frequency_first * (frequency_first - 1) // 2) * frequency_third

                # Only the second and third numbers are the same
                elif second_number == third_number:
                    answer += frequency_first * (frequency_second * (frequency_second - 1) // 2)

                # All 3 numbers are different
                else:
                    answer += frequency_first * frequency_second * frequency_third

                answer %= mod

    # Avoids returning negative number
    return answer

Big(O) Analysis

Time Complexity

O(n^2) – The solution first counts the frequency of each number, which takes O(n) time. Then, it iterates through all possible combinations of three numbers (i, j, k) from the input array. The outer loops implicitly iterate through possible values for 'i' and 'j', and the inner check determines 'k' such that i + j + k equals the target. This enumeration of pairs involves at most n^2 pairs. Calculating the number of triplets based on frequency counts within each pair takes constant time. Therefore, the overall time complexity is dominated by the nested iteration through potential pairs, leading to O(n^2) complexity.

Space Complexity

O(N) – The space complexity is dominated by the frequency count, which is stored in a hash map or array. In the worst case, where all the numbers in the input array are unique, the hash map will need to store N key-value pairs (number and its frequency), where N is the size of the input array. Therefore, the auxiliary space used scales linearly with the size of the input array. This leads to a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately as no triplets can be formed.
Array with fewer than 3 elements	Return 0 immediately because a triplet cannot be formed.
Large input array with potential integer overflow when calculating counts.	Use modulo arithmetic during count accumulation to prevent overflow.
Array contains all identical numbers	Handle this case by calculating combinations directly based on the element's count and target value.
Array contains negative numbers	The hashmap and two-pointer approaches will correctly account for negative numbers.
Array contains zeros	Zeros can be valid numbers in a triplet, so include them in calculations.
Target value is very large or small, such that no valid triplet exists.	The algorithm should naturally result in a count of 0 when no combination adds up to the target.
Large count of one specific number that causes integer overflow when calculating combination possibilities	Apply modulo to the intermediate calculation to prevent overflow.

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 values within the input array `arr`? Could there be negative numbers, zeros, or very large positive numbers?
What is the maximum size of the input array `arr`? This will help me consider potential time complexity constraints.
If there are multiple triplets that sum to `target`, should I return all of them, and if so, how should the result be formatted (e.g., a list of tuples, a list of lists)?
Is the order of elements within each triplet important? Should the triplets themselves be returned in a specific order?
If no triplets sum up to the target, what should I return (e.g., an empty list, null, or a specific error code)?

Brute Force Solution

Approach

The goal is to find groups of three numbers that add up to a specific target. The brute force approach simply tries every possible combination of three numbers from the given set.

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

Consider the first number in the set.
Pair that number with the second number in the set.
Now, for that pair, consider every other number in the set and see if the three numbers add up to the target.
If they do, count that combination.
If they don't, move to the next number.
Repeat steps 2-5 for every number in the set after the first number.
Repeat steps 1-6 for every number in the set.

Code Implementation

def three_sum_brute_force(numbers, target):    count = 0
    array_length = len(numbers)

    for first_number_index in range(array_length):

        for second_number_index in range(first_number_index + 1, array_length):
            # Ensures we don't repeat pairs by only considering later indices

            for third_number_index in range(second_number_index + 1, array_length):
                # Prevents duplicate triplets.

                if numbers[first_number_index] + numbers[second_number_index] + numbers[third_number_index] == target:
                    # Increment the count when a valid triplet is found.
                    count += 1

    return count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, count how many times each number appears in the list.
Then, consider all possible combinations of three numbers from the list, allowing for duplicates.
For each combination, check if their sum equals the target number.
If the sum is correct, calculate how many triplets of that exact combination exist based on the frequency counts of each number in that combination.
If the three numbers are all different, multiply their individual counts.
If two numbers are the same, use a combination formula to find the number of pairs you can form using the frequency count.
If all three numbers are the same, use a different combination formula to calculate the number of triplets.
Add up the number of triplets for all combinations that sum to the target. Make sure to apply modulo to the final answer to avoid overflow.

Code Implementation

from collections import Counter

def three_sum_multiplicity(array, target):
    frequency = Counter(array)
    keys = sorted(frequency.keys())
    mod = 10**9 + 7
    answer = 0

    for i in range(len(keys)):
        first_number = keys[i]
        for j in range(i, len(keys)):
            second_number = keys[j]
            third_number_needed = target - first_number - second_number

            if third_number_needed in frequency and third_number_needed >= second_number:
                third_number = third_number_needed
                frequency_first = frequency[first_number]
                frequency_second = frequency[second_number]
                frequency_third = frequency[third_number]

                # All 3 numbers are the same
                if first_number == second_number == third_number:
                    # Use combinations formula nCr = n! / (r! * (n-r)!) where r = 3
                    answer += (frequency_first * (frequency_first - 1) * (frequency_first - 2) // 6)

                # Only the first and second numbers are the same
                elif first_number == second_number:
                    # Use combinations formula nCr = n! / (r! * (n-r)!) where r = 2
                    answer += (frequency_first * (frequency_first - 1) // 2) * frequency_third

                # Only the second and third numbers are the same
                elif second_number == third_number:
                    answer += frequency_first * (frequency_second * (frequency_second - 1) // 2)

                # All 3 numbers are different
                else:
                    answer += frequency_first * frequency_second * frequency_third

                answer %= mod

    # Avoids returning negative number
    return answer

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately as no triplets can be formed.
Array with fewer than 3 elements	Return 0 immediately because a triplet cannot be formed.
Large input array with potential integer overflow when calculating counts.	Use modulo arithmetic during count accumulation to prevent overflow.
Array contains all identical numbers	Handle this case by calculating combinations directly based on the element's count and target value.
Array contains negative numbers	The hashmap and two-pointer approaches will correctly account for negative numbers.
Array contains zeros	Zeros can be valid numbers in a triplet, so include them in calculations.
Target value is very large or small, such that no valid triplet exists.	The algorithm should naturally result in a count of 0 when no combination adds up to the target.
Large count of one specific number that causes integer overflow when calculating combination possibilities	Apply modulo to the intermediate calculation to prevent overflow.