Jobs

Interviews

Discussions

4Sum

Medium

DE Shaw

1 view

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

Medium

DE Shaw

1 view

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:

What is the range of values for the integers in the input array? Can I expect negative numbers, zeros, or very large positive numbers?
Can the input array contain duplicate numbers, and if so, are duplicate quadruplets allowed in the output?
If there are multiple valid quadruplets that sum to the target, should I return all of them, or is it sufficient to return any one?
If no quadruplets sum up to the target value, what should I return? An empty list/array, or null?
Are the quadruplets in the output expected to be in any particular order (e.g., sorted ascending) or is the order arbitrary?

Brute Force Solution

Approach

We need to find four numbers from a given set that add up to a specific target value. The brute force method is like trying every possible combination of four numbers and checking if that combination hits the target.

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

Pick the first number from the set.
Pick a second number from the set.
Pick a third number from the set.
Pick a fourth number from the set.
Add these four numbers together.
Check if the sum of these four numbers equals the target value we are looking for.
If the sum equals the target, we found a valid combination. Save it.
Repeat these steps for every possible combination of four numbers from the set. Be systematic, making sure you don't miss any combination.
After trying all combinations, look at all the valid combinations we saved. Make sure to remove any duplicate combinations before presenting the final result.

Code Implementation

def four_sum_brute_force(numbers, target):
    list_of_valid_quadruplets = []

    for first_index in range(len(numbers)):
        for second_index in range(first_index + 1, len(numbers)):
            for third_index in range(second_index + 1, len(numbers)):
                for fourth_index in range(third_index + 1, len(numbers)):
                    # We have a combination; now check the sum
                    sum_of_quadruplet = numbers[first_index] + numbers[second_index] +\
                                          numbers[third_index] + numbers[fourth_index]

                    if sum_of_quadruplet == target:
                        # We need to sort to easily identify duplicates
                        quadruplet = sorted([numbers[first_index], numbers[second_index],\
                                              numbers[third_index], numbers[fourth_index]])

                        # Check if this sorted quadruplet is already in our results
                        if quadruplet not in list_of_valid_quadruplets:
                            # Avoid duplicates in our final answer
                            list_of_valid_quadruplets.append(quadruplet)

    return list_of_valid_quadruplets

Big(O) Analysis

Time Complexity

O(n^4) – The brute force approach iterates through the input array nums of size n four times to select four numbers. These four nested loops contribute a factor of n each. After selecting each quadruplet, we sum them up, which takes constant time O(1), and compare the sum with the target, which is another O(1) operation. Removing duplicate quadruplets has a cost, but is less than the cost of enumerating the quadruplets, so it doesn't affect the overall time complexity. Therefore, the total number of operations is proportional to n * n * n * n, which simplifies to O(n^4).

Space Complexity

O(N^4) – The described brute force method requires storing the valid combinations found. In the worst-case scenario, every combination of four numbers could sum up to the target, leading to a number of combinations proportional to N choose 4, or O(N^4). Since we need to store each of these combinations (each containing four numbers), the space required to store all valid combinations is O(N^4). Additionally, to remove duplicate combinations, we might need to store all combinations in a set-like data structure, which would also take O(N^4) space in the worst case. Therefore, the space complexity is O(N^4).

Optimal Solution

Approach

The most efficient way to solve this is to avoid checking every possible combination. Instead, we use a clever ordering and narrowing of our search to quickly find the groups of four numbers that add up to the target. This involves sorting the numbers and strategically moving through them.

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

First, put all the numbers in order from smallest to largest. This will help us skip possibilities later.
Pick the first number. Then, pick a second number after the first.
Now, instead of picking the third and fourth numbers randomly, start with one number near the beginning (after the second) and another number near the end of the ordered list.
Add the four numbers together. If the sum is too small, move the number near the beginning forward to try a slightly bigger number. If the sum is too big, move the number near the end backward to try a slightly smaller number.
Keep adjusting those two inside numbers until you find a combination that equals the target. If you've moved the two inside numbers past each other, it means there are no more combinations that work with the first two numbers you picked.
Move to the next possible second number and repeat the process of adjusting the inside numbers. Do this for every possible first and second number.
Because the numbers are ordered, we can easily skip over duplicate combinations and focus on unique sets of four.

Code Implementation

def four_sum(numbers, target):
    numbers.sort()
    quadruplets = []
    number_of_elements = len(numbers)

    for first_number_index in range(number_of_elements - 3):
        # Prevents duplicate quadruplets in result
        if first_number_index > 0 and numbers[first_number_index] == numbers[first_number_index - 1]:
            continue

        for second_number_index in range(first_number_index + 1, number_of_elements - 2):
            # Prevents duplicate quadruplets in result
            if second_number_index > first_number_index + 1 and numbers[second_number_index] == numbers[second_number_index - 1]:
                continue

            left_number_index = second_number_index + 1
            right_number_index = number_of_elements - 1

            while left_number_index < right_number_index:
                current_sum = numbers[first_number_index] + numbers[second_number_index] + numbers[left_number_index] + numbers[right_number_index]

                if current_sum == target:
                    quadruplets.append([numbers[first_number_index], numbers[second_number_index], numbers[left_number_index], numbers[right_number_index]])
                    # Avoids duplicate triplets
                    while left_number_index < right_number_index and numbers[left_number_index] == numbers[left_number_index + 1]:
                        left_number_index += 1

                    # Avoids duplicate triplets
                    while left_number_index < right_number_index and numbers[right_number_index] == numbers[right_number_index - 1]:
                        right_number_index -= 1

                    left_number_index += 1
                    right_number_index -= 1
                elif current_sum < target:
                    # Sum is too small, move left pointer to increase sum.
                    left_number_index += 1
                else:
                    # Sum is too large, move right pointer to decrease sum.
                    right_number_index -= 1

    return quadruplets

Big(O) Analysis

Time Complexity

O(n^3) – The algorithm sorts the input array of size n, which takes O(n log n) time. Then, it iterates through all possible pairs of the first two numbers using nested loops, contributing O(n^2). For each pair, a two-pointer approach is used to find the remaining two numbers that sum to the target, taking O(n) time in the worst case. Thus, the overall time complexity is dominated by the nested loops and the two-pointer search, resulting in approximately n * n * n operations. Therefore, the time complexity is O(n^3).

Space Complexity

O(1) – The described solution sorts the input array in-place, meaning no extra array of size N is created for sorting. Only a few integer variables like 'first', 'second', 'left', 'right', and 'sum' are used to store indices and intermediate sums during the two-pointer approach. The number of these variables remains constant irrespective of the input array's size (N). Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Null input array	Throw an IllegalArgumentException or return an empty list to avoid NullPointerException.
Array size less than 4	Return an empty list since a 4-sum combination is impossible.
Input array with all identical numbers.	Correctly handles duplicate numbers by skipping over same elements in inner loops after the first occurence for each distinct number.
Large input array with numbers close to INT_MAX or INT_MIN.	Potential integer overflow during summation, consider using long data type for intermediate sums.
Target value is extremely large or small.	The algorithm should still function correctly, assuming no integer overflow during sum calculation.
No valid 4-sum combinations exist.	Return an empty list to indicate that no solution was found.
Input array contains duplicate quadruplets that sum to the target.	Sort each quadruplet and add it to a set to avoid duplicate quadruplets in the result.
Presence of zero in the input array.	Handle zero appropriately; including it may or may not lead to a valid quadruplet so ensure the counts of zero are correctly handled.

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 for the integers in the input array? Can I expect negative numbers, zeros, or very large positive numbers?
Can the input array contain duplicate numbers, and if so, are duplicate quadruplets allowed in the output?
If there are multiple valid quadruplets that sum to the target, should I return all of them, or is it sufficient to return any one?
If no quadruplets sum up to the target value, what should I return? An empty list/array, or null?
Are the quadruplets in the output expected to be in any particular order (e.g., sorted ascending) or is the order arbitrary?

Brute Force Solution

Approach

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

Pick the first number from the set.
Pick a second number from the set.
Pick a third number from the set.
Pick a fourth number from the set.
Add these four numbers together.
Check if the sum of these four numbers equals the target value we are looking for.
If the sum equals the target, we found a valid combination. Save it.
Repeat these steps for every possible combination of four numbers from the set. Be systematic, making sure you don't miss any combination.
After trying all combinations, look at all the valid combinations we saved. Make sure to remove any duplicate combinations before presenting the final result.

Code Implementation

def four_sum_brute_force(numbers, target):
    list_of_valid_quadruplets = []

    for first_index in range(len(numbers)):
        for second_index in range(first_index + 1, len(numbers)):
            for third_index in range(second_index + 1, len(numbers)):
                for fourth_index in range(third_index + 1, len(numbers)):
                    # We have a combination; now check the sum
                    sum_of_quadruplet = numbers[first_index] + numbers[second_index] +\
                                          numbers[third_index] + numbers[fourth_index]

                    if sum_of_quadruplet == target:
                        # We need to sort to easily identify duplicates
                        quadruplet = sorted([numbers[first_index], numbers[second_index],\
                                              numbers[third_index], numbers[fourth_index]])

                        # Check if this sorted quadruplet is already in our results
                        if quadruplet not in list_of_valid_quadruplets:
                            # Avoid duplicates in our final answer
                            list_of_valid_quadruplets.append(quadruplet)

    return list_of_valid_quadruplets

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, put all the numbers in order from smallest to largest. This will help us skip possibilities later.
Pick the first number. Then, pick a second number after the first.
Now, instead of picking the third and fourth numbers randomly, start with one number near the beginning (after the second) and another number near the end of the ordered list.
Add the four numbers together. If the sum is too small, move the number near the beginning forward to try a slightly bigger number. If the sum is too big, move the number near the end backward to try a slightly smaller number.
Keep adjusting those two inside numbers until you find a combination that equals the target. If you've moved the two inside numbers past each other, it means there are no more combinations that work with the first two numbers you picked.
Move to the next possible second number and repeat the process of adjusting the inside numbers. Do this for every possible first and second number.
Because the numbers are ordered, we can easily skip over duplicate combinations and focus on unique sets of four.

Code Implementation

def four_sum(numbers, target):
    numbers.sort()
    quadruplets = []
    number_of_elements = len(numbers)

    for first_number_index in range(number_of_elements - 3):
        # Prevents duplicate quadruplets in result
        if first_number_index > 0 and numbers[first_number_index] == numbers[first_number_index - 1]:
            continue

        for second_number_index in range(first_number_index + 1, number_of_elements - 2):
            # Prevents duplicate quadruplets in result
            if second_number_index > first_number_index + 1 and numbers[second_number_index] == numbers[second_number_index - 1]:
                continue

            left_number_index = second_number_index + 1
            right_number_index = number_of_elements - 1

            while left_number_index < right_number_index:
                current_sum = numbers[first_number_index] + numbers[second_number_index] + numbers[left_number_index] + numbers[right_number_index]

                if current_sum == target:
                    quadruplets.append([numbers[first_number_index], numbers[second_number_index], numbers[left_number_index], numbers[right_number_index]])
                    # Avoids duplicate triplets
                    while left_number_index < right_number_index and numbers[left_number_index] == numbers[left_number_index + 1]:
                        left_number_index += 1

                    # Avoids duplicate triplets
                    while left_number_index < right_number_index and numbers[right_number_index] == numbers[right_number_index - 1]:
                        right_number_index -= 1

                    left_number_index += 1
                    right_number_index -= 1
                elif current_sum < target:
                    # Sum is too small, move left pointer to increase sum.
                    left_number_index += 1
                else:
                    # Sum is too large, move right pointer to decrease sum.
                    right_number_index -= 1

    return quadruplets

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null input array	Throw an IllegalArgumentException or return an empty list to avoid NullPointerException.
Array size less than 4	Return an empty list since a 4-sum combination is impossible.
Input array with all identical numbers.	Correctly handles duplicate numbers by skipping over same elements in inner loops after the first occurence for each distinct number.
Large input array with numbers close to INT_MAX or INT_MIN.	Potential integer overflow during summation, consider using long data type for intermediate sums.
Target value is extremely large or small.	The algorithm should still function correctly, assuming no integer overflow during sum calculation.
No valid 4-sum combinations exist.	Return an empty list to indicate that no solution was found.
Input array contains duplicate quadruplets that sum to the target.	Sort each quadruplet and add it to a set to avoid duplicate quadruplets in the result.
Presence of zero in the input array.	Handle zero appropriately; including it may or may not lead to a valid quadruplet so ensure the counts of zero are correctly handled.