Jobs

Interviews

Discussions

4Sum

#3 Most AskedMedium

4Sum #3 Most Asked

Medium

Cloudflare

35 views

Topics:

ArraysTwo Pointers

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

0 <= a, b, c, d < n
a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Example 1:

Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2:

Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]

Constraints:

1 <= nums.length <= 200
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹

Try coding it in LeetCode

4Sum

#3 Most AskedMedium

4Sum #3 Most Asked

Medium

Cloudflare

35 views

Topics:

ArraysTwo Pointers

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

0 <= a, b, c, d < n
a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Example 1:

Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2:

Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]

Constraints:

1 <= nums.length <= 200
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹

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:

Are there any constraints on the size of the input array `nums` or the range of integer values within it?
Can the input array `nums` contain duplicate numbers, and if so, how should duplicate quadruplets in the output be handled?
What should be returned if no quadruplets sum up to the target?
Does the order of numbers within a quadruplet matter for uniqueness (e.g., [1, 2, 3, 4] vs [4, 3, 2, 1])?
Are the numbers in the input array guaranteed to be distinct, or can they be negative or zero?

Brute Force Solution

Approach

The brute force approach to finding four numbers that add up to a target sum is to systematically check every single combination of four numbers from the given collection. We'll go through all possible groups of four and see if their sum matches what we're looking for.

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

Pick the first number from the collection.
Then, from the remaining numbers, pick a second number.
Next, from the numbers that are still left, pick a third number.
Finally, from the numbers that haven't been picked yet, pick a fourth number.
Add these four chosen numbers together.
Check if their sum is exactly equal to the target sum.
If it is, we've found a valid group. Keep track of this group.
Now, go back and try picking a different fourth number, then a different third number, then a different second number, and finally a different first number. Essentially, try every single possible unique combination of four numbers.
Continue this process until you have checked every possible combination of four numbers from the original collection.
All the groups of four numbers that added up to the target sum are your solutions.

Code Implementation

def four_sum_brute_force(numbers, target_sum):    found_quadruplets = []    number_count = len(numbers)    # We need four distinct numbers, so we iterate up to number_count - 3 for the first number    for first_index in range(number_count - 3):        # The second number must come after the first, so we start from first_index + 1        for second_index in range(first_index + 1, number_count - 2):            # The third number must come after the second            for third_index in range(second_index + 1, number_count - 1):                # The fourth number must come after the third                for fourth_index in range(third_index + 1, number_count):                    current_sum = (numbers[first_index] + numbers[second_index] +                                   numbers[third_index] + numbers[fourth_index])                    # Check if the sum of the four chosen numbers equals the target sum                    if current_sum == target_sum:                        quadruplet = [numbers[first_index], numbers[second_index],                                      numbers[third_index], numbers[fourth_index]]                        found_quadruplets.append(quadruplet)    return found_quadruplets

Big(O) Analysis

Time Complexity

O(n^4) – The brute force approach involves four nested loops to pick four distinct numbers from the input array of size n. The outermost loop picks the first number, the second loop picks the second from the remaining, the third picks the third from what's left, and the innermost loop picks the fourth. Each loop iterates up to n times. Thus, the total number of operations is roughly n * n * n * n, leading to a time complexity of O(n^4).

Space Complexity

O(1) – The brute-force approach described involves nested loops to iterate through combinations of four numbers. No auxiliary data structures are explicitly created to store intermediate results or process the input beyond a few variables to hold the current combination and indices. Therefore, the auxiliary space complexity is constant, independent of the input size N.

Optimal Solution

Approach

The most efficient way to find all unique combinations of four numbers that add up to a target sum involves a process of elimination and clever searching. We'll sort the numbers first, which is a key step to avoiding duplicate combinations and speeding up the search.

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

Imagine you have a collection of numbers and you're looking for four of them that add up to a specific target. The first thing to do is arrange all the numbers in order from smallest to largest. This makes it much easier to manage and avoid repeating the same groups of numbers.
Now, pick the very first number from the sorted collection and temporarily set it aside. Think of it as the 'first number' in a potential group of four.
Next, take the second number from the sorted collection and set it aside as the 'second number' of the potential group. You've now picked two numbers.
With the remaining numbers, you need to find two more that, when added to the two you've already picked, will equal your target sum. The challenge is to do this without checking every single pair from the rest of the numbers.
Since the remaining numbers are also sorted, you can use a special technique. Imagine you have two pointers, one starting at the beginning of the remaining numbers and one at the end. You look at the sum of the numbers pointed to by these two pointers and compare it to what's needed to reach the target (which is the original target minus the first two numbers you picked).
If the sum is too small, you need larger numbers, so you move the 'start' pointer one step forward. If the sum is too large, you need smaller numbers, so you move the 'end' pointer one step backward.
You keep doing this 'pointer dance' until the pointers meet. If at any point the sum of the two numbers pointed to is exactly what you need, you've found a valid group of four. Add this group to your results.
When you've finished the pointer dance for a particular 'second number', you move on to the next possible 'second number' and repeat the pointer dance process.
After you've tried all possible 'second numbers' for the current 'first number', you move on to the next possible 'first number' and start the whole process again, picking a new 'first number' and then trying all possible 'second numbers' and their corresponding pairs.
A crucial part is skipping over duplicate numbers. If you've just used a '3' as your 'first number', and the next number is also a '3', you should skip it to avoid generating the exact same combination of four numbers again. The same applies to the 'second number' and the numbers found by the pointers.
By systematically picking the first two numbers and then efficiently searching for the last two using the ordered collection and the two-pointer technique, you can find all unique combinations without exhaustive checking.

Code Implementation

def find_four_sum_combinations(sorted_numbers, target_sum_quadruplet):
    quadruplets = []
    numbers_count = len(sorted_numbers)

    if numbers_count < 4:
        return quadruplets

    sorted_numbers.sort()

    # Iterate through the first number of the potential quadruplet.
    for first_number_index in range(numbers_count - 3):
        # Skip duplicate first numbers to avoid redundant combinations.
        if first_number_index > 0 and sorted_numbers[first_number_index] == sorted_numbers[first_number_index - 1]:
            continue

        # Iterate through the second number of the potential quadruplet.
        for second_number_index in range(first_number_index + 1, numbers_count - 2):
            # Skip duplicate second numbers.
            if second_number_index > first_number_index + 1 and sorted_numbers[second_number_index] == sorted_numbers[second_number_index - 1]:
                continue

            remaining_target_sum = target_sum_quadruplet - sorted_numbers[first_number_index] - sorted_numbers[second_number_index]
            third_number_index = second_number_index + 1
            fourth_number_index = numbers_count - 1

            # Use two pointers to find the remaining two numbers efficiently.
            while third_number_index < fourth_number_index:
                current_pair_sum = sorted_numbers[third_number_index] + sorted_numbers[fourth_number_index]

                if current_pair_sum == remaining_target_sum:
                    quadruplets.append([
                        sorted_numbers[first_number_index],
                        sorted_numbers[second_number_index],
                        sorted_numbers[third_number_index],
                        sorted_numbers[fourth_number_index]
                    ])

                    # Skip duplicate third numbers.
                    while third_number_index < fourth_number_index and sorted_numbers[third_number_index] == sorted_numbers[third_number_index + 1]:
                        third_number_index += 1
                    # Skip duplicate fourth numbers.
                    while third_number_index < fourth_number_index and sorted_numbers[fourth_number_index] == sorted_numbers[fourth_number_index - 1]:
                        fourth_number_index -= 1

                    third_number_index += 1
                    fourth_number_index -= 1
                elif current_pair_sum < remaining_target_sum:
                    third_number_index += 1
                else:
                    fourth_number_index -= 1

    return quadruplets

Big(O) Analysis

Time Complexity

O(n³) – The solution begins with sorting the input array, which takes O(n log n) time. Then, there are two outer loops that iterate through the array to pick the first two numbers, contributing O(n²) iterations. Inside these loops, a two-pointer approach is used to find the remaining two numbers in the rest of the sorted array. This two-pointer scan, on average, takes O(n) time for each pair of outer loop selections. Therefore, the dominant factor becomes the nested loops combined with the two-pointer scan, resulting in an overall time complexity of O(n³).

Space Complexity

O(1) or O(k) – The algorithm primarily uses a few integer variables for pointers and indices (i, j, left, right) and the target sum, which contribute constant auxiliary space, O(1). The most significant auxiliary space comes from storing the result: a list of quadruplets. If k is the number of unique quadruplets found, the space complexity for the output storage is O(k). Since k can be at most O(n^4) in the worst case, but is often much smaller and doesn't depend on intermediate data structures that scale with n, the auxiliary space is dominated by the output or is considered O(1) if we exclude output storage.

Edge Cases

Case	How to Handle
Input array is null or empty	The solution should return an empty list as no quadruplets can be formed.
Input array has fewer than 4 elements	If the array size is less than 4, return an empty list immediately because a quadruplet cannot be formed.
Array contains all identical values	The solution must correctly identify all unique quadruplets, even if multiple combinations use the same identical values, by carefully managing indices and skipping duplicates.
Array contains negative numbers and zeros	The algorithm should handle sums involving negative numbers and zeros correctly without any special modifications.
The target value is very large or very small, potentially leading to integer overflow	Use of 64-bit integers (long long in C++, long in Java) for sum calculations will prevent overflow issues.
Multiple valid quadruplets exist	The solution must find and return all unique quadruplets, ensuring no duplicates in the output list.
No valid quadruplets sum to the target	The algorithm naturally handles this by returning an empty list if no combinations satisfy the condition.
Large input array size	The chosen approach, typically sorting followed by a k-sum generalization, should be efficient enough to pass within time limits, often O(n^3) or O(n^4) depending on implementation details.

Input array is null or empty

How to Handle:

The solution should return an empty list as no quadruplets can be formed.

Input array has fewer than 4 elements

How to Handle:

If the array size is less than 4, return an empty list immediately because a quadruplet cannot be formed.

Array contains all identical values

How to Handle:

The solution must correctly identify all unique quadruplets, even if multiple combinations use the same identical values, by carefully managing indices and skipping duplicates.

Array contains negative numbers and zeros

How to Handle:

The algorithm should handle sums involving negative numbers and zeros correctly without any special modifications.

The target value is very large or very small, potentially leading to integer overflow

How to Handle:

Use of 64-bit integers (long long in C++, long in Java) for sum calculations will prevent overflow issues.

Multiple valid quadruplets exist

How to Handle:

The solution must find and return all unique quadruplets, ensuring no duplicates in the output list.

No valid quadruplets sum to the target

How to Handle:

The algorithm naturally handles this by returning an empty list if no combinations satisfy the condition.

Large input array size

How to Handle:

The chosen approach, typically sorting followed by a k-sum generalization, should be efficient enough to pass within time limits, often O(n^3) or O(n^4) depending on implementation details.

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:

Are there any constraints on the size of the input array `nums` or the range of integer values within it?
Can the input array `nums` contain duplicate numbers, and if so, how should duplicate quadruplets in the output be handled?
What should be returned if no quadruplets sum up to the target?
Does the order of numbers within a quadruplet matter for uniqueness (e.g., [1, 2, 3, 4] vs [4, 3, 2, 1])?
Are the numbers in the input array guaranteed to be distinct, or can they be negative or zero?

Brute Force Solution

Approach

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

Pick the first number from the collection.
Then, from the remaining numbers, pick a second number.
Next, from the numbers that are still left, pick a third number.
Finally, from the numbers that haven't been picked yet, pick a fourth number.
Add these four chosen numbers together.
Check if their sum is exactly equal to the target sum.
If it is, we've found a valid group. Keep track of this group.
Now, go back and try picking a different fourth number, then a different third number, then a different second number, and finally a different first number. Essentially, try every single possible unique combination of four numbers.
Continue this process until you have checked every possible combination of four numbers from the original collection.
All the groups of four numbers that added up to the target sum are your solutions.

Code Implementation

def four_sum_brute_force(numbers, target_sum):    found_quadruplets = []    number_count = len(numbers)    # We need four distinct numbers, so we iterate up to number_count - 3 for the first number    for first_index in range(number_count - 3):        # The second number must come after the first, so we start from first_index + 1        for second_index in range(first_index + 1, number_count - 2):            # The third number must come after the second            for third_index in range(second_index + 1, number_count - 1):                # The fourth number must come after the third                for fourth_index in range(third_index + 1, number_count):                    current_sum = (numbers[first_index] + numbers[second_index] +                                   numbers[third_index] + numbers[fourth_index])                    # Check if the sum of the four chosen numbers equals the target sum                    if current_sum == target_sum:                        quadruplet = [numbers[first_index], numbers[second_index],                                      numbers[third_index], numbers[fourth_index]]                        found_quadruplets.append(quadruplet)    return found_quadruplets

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine you have a collection of numbers and you're looking for four of them that add up to a specific target. The first thing to do is arrange all the numbers in order from smallest to largest. This makes it much easier to manage and avoid repeating the same groups of numbers.
Now, pick the very first number from the sorted collection and temporarily set it aside. Think of it as the 'first number' in a potential group of four.
Next, take the second number from the sorted collection and set it aside as the 'second number' of the potential group. You've now picked two numbers.
With the remaining numbers, you need to find two more that, when added to the two you've already picked, will equal your target sum. The challenge is to do this without checking every single pair from the rest of the numbers.
Since the remaining numbers are also sorted, you can use a special technique. Imagine you have two pointers, one starting at the beginning of the remaining numbers and one at the end. You look at the sum of the numbers pointed to by these two pointers and compare it to what's needed to reach the target (which is the original target minus the first two numbers you picked).
If the sum is too small, you need larger numbers, so you move the 'start' pointer one step forward. If the sum is too large, you need smaller numbers, so you move the 'end' pointer one step backward.
You keep doing this 'pointer dance' until the pointers meet. If at any point the sum of the two numbers pointed to is exactly what you need, you've found a valid group of four. Add this group to your results.
When you've finished the pointer dance for a particular 'second number', you move on to the next possible 'second number' and repeat the pointer dance process.
After you've tried all possible 'second numbers' for the current 'first number', you move on to the next possible 'first number' and start the whole process again, picking a new 'first number' and then trying all possible 'second numbers' and their corresponding pairs.
A crucial part is skipping over duplicate numbers. If you've just used a '3' as your 'first number', and the next number is also a '3', you should skip it to avoid generating the exact same combination of four numbers again. The same applies to the 'second number' and the numbers found by the pointers.
By systematically picking the first two numbers and then efficiently searching for the last two using the ordered collection and the two-pointer technique, you can find all unique combinations without exhaustive checking.

Code Implementation

def find_four_sum_combinations(sorted_numbers, target_sum_quadruplet):
    quadruplets = []
    numbers_count = len(sorted_numbers)

    if numbers_count < 4:
        return quadruplets

    sorted_numbers.sort()

    # Iterate through the first number of the potential quadruplet.
    for first_number_index in range(numbers_count - 3):
        # Skip duplicate first numbers to avoid redundant combinations.
        if first_number_index > 0 and sorted_numbers[first_number_index] == sorted_numbers[first_number_index - 1]:
            continue

        # Iterate through the second number of the potential quadruplet.
        for second_number_index in range(first_number_index + 1, numbers_count - 2):
            # Skip duplicate second numbers.
            if second_number_index > first_number_index + 1 and sorted_numbers[second_number_index] == sorted_numbers[second_number_index - 1]:
                continue

            remaining_target_sum = target_sum_quadruplet - sorted_numbers[first_number_index] - sorted_numbers[second_number_index]
            third_number_index = second_number_index + 1
            fourth_number_index = numbers_count - 1

            # Use two pointers to find the remaining two numbers efficiently.
            while third_number_index < fourth_number_index:
                current_pair_sum = sorted_numbers[third_number_index] + sorted_numbers[fourth_number_index]

                if current_pair_sum == remaining_target_sum:
                    quadruplets.append([
                        sorted_numbers[first_number_index],
                        sorted_numbers[second_number_index],
                        sorted_numbers[third_number_index],
                        sorted_numbers[fourth_number_index]
                    ])

                    # Skip duplicate third numbers.
                    while third_number_index < fourth_number_index and sorted_numbers[third_number_index] == sorted_numbers[third_number_index + 1]:
                        third_number_index += 1
                    # Skip duplicate fourth numbers.
                    while third_number_index < fourth_number_index and sorted_numbers[fourth_number_index] == sorted_numbers[fourth_number_index - 1]:
                        fourth_number_index -= 1

                    third_number_index += 1
                    fourth_number_index -= 1
                elif current_pair_sum < remaining_target_sum:
                    third_number_index += 1
                else:
                    fourth_number_index -= 1

    return quadruplets

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input array is null or empty	The solution should return an empty list as no quadruplets can be formed.
Input array has fewer than 4 elements	If the array size is less than 4, return an empty list immediately because a quadruplet cannot be formed.
Array contains all identical values	The solution must correctly identify all unique quadruplets, even if multiple combinations use the same identical values, by carefully managing indices and skipping duplicates.
Array contains negative numbers and zeros	The algorithm should handle sums involving negative numbers and zeros correctly without any special modifications.
The target value is very large or very small, potentially leading to integer overflow	Use of 64-bit integers (long long in C++, long in Java) for sum calculations will prevent overflow issues.
Multiple valid quadruplets exist	The solution must find and return all unique quadruplets, ensuring no duplicates in the output list.
No valid quadruplets sum to the target	The algorithm naturally handles this by returning an empty list if no combinations satisfy the condition.
Large input array size	The chosen approach, typically sorting followed by a k-sum generalization, should be efficient enough to pass within time limits, often O(n^3) or O(n^4) depending on implementation details.

Input array is null or empty

How to Handle:

The solution should return an empty list as no quadruplets can be formed.

Input array has fewer than 4 elements

How to Handle:

If the array size is less than 4, return an empty list immediately because a quadruplet cannot be formed.

Array contains all identical values

How to Handle:

The solution must correctly identify all unique quadruplets, even if multiple combinations use the same identical values, by carefully managing indices and skipping duplicates.

Array contains negative numbers and zeros

How to Handle:

The algorithm should handle sums involving negative numbers and zeros correctly without any special modifications.

The target value is very large or very small, potentially leading to integer overflow

How to Handle:

Use of 64-bit integers (long long in C++, long in Java) for sum calculations will prevent overflow issues.

Multiple valid quadruplets exist

How to Handle:

The solution must find and return all unique quadruplets, ensuring no duplicates in the output list.

No valid quadruplets sum to the target

How to Handle:

The algorithm naturally handles this by returning an empty list if no combinations satisfy the condition.

Large input array size

How to Handle:

The chosen approach, typically sorting followed by a k-sum generalization, should be efficient enough to pass within time limits, often O(n^3) or O(n^4) depending on implementation details.

0/10 Cloudflare questions completed

0/10 completed