Jobs

Interviews

Discussions

3Sum

Medium

Apple

4 views

Topics:

ArraysTwo Pointers

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

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

Example 2:

Input: nums = [0,1,1]
Output: []

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]

Constraints:

3 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5

3Sum

Medium

Apple

4 views

Topics:

ArraysTwo Pointers

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

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

Example 2:

Input: nums = [0,1,1]
Output: []

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]

Constraints:

3 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5

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, and how large can the input array (nums) be?
Can the input array contain duplicate numbers, and if so, how should that be handled to ensure unique triplets in the output?
If no triplets sum to zero, what should the return value be (e.g., an empty list, null)?
Is the order of triplets in the output important, or can they be in any order? Should the numbers within each triplet be sorted?
Can the input array be empty or null? If so, how should I handle these edge cases?

Brute Force Solution

Approach

The problem asks us to find combinations of three numbers that add up to zero. The brute force method means we will check every single possible combination of three numbers from the given set. If a combination adds up to zero, we keep it; otherwise, we move on to the next combination.

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.
Add these three numbers together.
Check if the sum is equal to zero.
If the sum is zero, save this combination of numbers.
Repeat the process by picking different combinations of the three numbers until you have tried every possible combination.
Return all the saved combinations that add up to zero, but make sure there are no duplicate combinations in the final result.

Code Implementation

def three_sum_brute_force(numbers):
    result = []
    numbers_length = len(numbers)

    for first_index in range(numbers_length):
        for second_index in range(first_index + 1, numbers_length):
            for third_index in range(second_index + 1, numbers_length):
                first_number = numbers[first_index]
                second_number = numbers[second_index]
                third_number = numbers[third_index]

                sum_of_numbers = first_number + second_number + third_number

                # Check if the current combination sums to zero.
                if sum_of_numbers == 0:

                    current_combination = sorted([first_number, second_number, third_number])

                    # Avoid adding duplicate triplets to the result.
                    if current_combination not in result:

                        result.append(current_combination)

    # Return the unique triplets that sum to zero.
    return result

Big(O) Analysis

Time Complexity

O(n³) – The described brute force approach involves picking three numbers from the input array of size n. This implies three nested loops, each iterating through the array. The first loop iterates n times, the second also iterates n times, and the third iterates n times. Therefore, the total number of operations is proportional to n * n * n, resulting in a time complexity of O(n³).

Space Complexity

O(N) – The provided brute force algorithm described will store each valid combination of three numbers that sum to zero. In the worst-case scenario, where a significant portion of the combinations sum to zero, the algorithm needs to maintain a list of these combinations. The size of this list could potentially grow linearly with the number of possible combinations derived from the input array of size N. Therefore, the auxiliary space complexity is O(N), representing the potential size of the list holding the combinations.

Optimal Solution

Approach

The key to efficiently finding sets of three numbers that sum to zero involves avoiding redundant calculations by strategically narrowing down possibilities. First we sort the numbers, then we use a two-pointer approach to quickly explore potential pairs that complement a fixed number.

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

Begin by arranging the list of numbers in ascending order from smallest to largest.
Consider each number in the list, one at a time. For each number, we'll try to find two other numbers that, when added to it, result in zero.
To find these two numbers, imagine pointers at both ends of the remaining portion of the list (excluding the number currently being considered).
Add the numbers pointed to by the two pointers. If the sum equals the negative of the current number, then we have found a valid triplet. Record this triplet.
If the sum is less than the negative of the current number, shift the left pointer one position to the right, seeking a larger value.
If the sum is greater than the negative of the current number, shift the right pointer one position to the left, seeking a smaller value.
Repeat the pointer adjustments until the pointers cross each other. If no triplet is found during this process, move on to the next number in the list.
When considering each number, make sure to skip over any duplicate numbers to avoid generating duplicate triplets.
The list of recorded triplets is the result.

Code Implementation

def find_triplets_that_sum_to_zero(numbers):
    numbers.sort()
    triplets = []
    numbers_length = len(numbers)

    for i in range(numbers_length - 2):
        # Avoid duplicates for the first number
        if i > 0 and numbers[i] == numbers[i - 1]:
            continue

        left_pointer = i + 1
        right_pointer = numbers_length - 1

        while left_pointer < right_pointer:
            current_sum = numbers[i] + numbers[left_pointer] + numbers[right_pointer]

            if current_sum == 0:
                triplets.append([numbers[i], numbers[left_pointer], numbers[right_pointer]])

                # Avoid duplicates for the second number
                while left_pointer < right_pointer and numbers[left_pointer] == numbers[left_pointer + 1]:
                    left_pointer += 1

                # Avoid duplicates for the third number
                while left_pointer < right_pointer and numbers[right_pointer] == numbers[right_pointer - 1]:
                    right_pointer -= 1

                left_pointer += 1
                right_pointer -= 1

            elif current_sum < 0:
                left_pointer += 1 # Need a larger sum

            else:
                right_pointer -= 1 # Need a smaller sum

    return triplets

Big(O) Analysis

Time Complexity

O(n²) – The algorithm begins by sorting the input array of size n, which takes O(n log n) time. After sorting, the algorithm iterates through each element of the sorted array (outer loop - n iterations). For each element, a two-pointer approach is used on the remaining part of the array which requires at most n comparisons in the worst case (inner while loop). Thus, the dominant operation involves the nested loop structure that approximates n * n/2 operations. Therefore the time complexity is O(n²), as we drop the n log n from sorting and the constant factor of 1/2.

Space Complexity

O(1) – The algorithm primarily sorts the input array in-place, and uses a fixed number of integer variables for pointers and sums. The recorded triplets are stored in a list; however, the problem statement does not explicitly mention constraints on the number of triplets. If we assume a constant number of triplets can be stored, then the space needed remains constant regardless of the input size N. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty list immediately as no triplets can be formed.
Array with less than 3 elements	Return an empty list since a triplet cannot be formed.
Array with all identical numbers (e.g., all zeros)	The solution should handle duplicate values correctly, ensuring only unique triplets are added to the result, and avoiding issues like [0, 0, 0], [0, 0, 0], etc.
Array with many duplicate numbers	The solution must avoid generating duplicate triplets by skipping over consecutive duplicate numbers after sorting the array.
Array with large positive and negative numbers that could potentially lead to integer overflow during summation	Using a language with automatic overflow handling or employing appropriate checks within the summation can prevent potential overflow errors.
Array contains a large number of zeros.	The solution should handle the case where multiple zeros are present in the array, ensuring that triplets containing zeros are identified and duplicates are avoided.
No triplets sum to zero.	The solution should return an empty list if no such triplets exist.
Input array is very large (potential performance bottleneck)	Sorting the array first (O(n log n)) and then using two pointers to find triplets (O(n^2)) ensures an optimal solution with a time complexity of O(n^2).

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, and how large can the input array (nums) be?
Can the input array contain duplicate numbers, and if so, how should that be handled to ensure unique triplets in the output?
If no triplets sum to zero, what should the return value be (e.g., an empty list, null)?
Is the order of triplets in the output important, or can they be in any order? Should the numbers within each triplet be sorted?
Can the input array be empty or null? If so, how should I handle these edge cases?

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.
Add these three numbers together.
Check if the sum is equal to zero.
If the sum is zero, save this combination of numbers.
Repeat the process by picking different combinations of the three numbers until you have tried every possible combination.
Return all the saved combinations that add up to zero, but make sure there are no duplicate combinations in the final result.

Code Implementation

def three_sum_brute_force(numbers):
    result = []
    numbers_length = len(numbers)

    for first_index in range(numbers_length):
        for second_index in range(first_index + 1, numbers_length):
            for third_index in range(second_index + 1, numbers_length):
                first_number = numbers[first_index]
                second_number = numbers[second_index]
                third_number = numbers[third_index]

                sum_of_numbers = first_number + second_number + third_number

                # Check if the current combination sums to zero.
                if sum_of_numbers == 0:

                    current_combination = sorted([first_number, second_number, third_number])

                    # Avoid adding duplicate triplets to the result.
                    if current_combination not in result:

                        result.append(current_combination)

    # Return the unique triplets that sum to zero.
    return result

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Begin by arranging the list of numbers in ascending order from smallest to largest.
Consider each number in the list, one at a time. For each number, we'll try to find two other numbers that, when added to it, result in zero.
To find these two numbers, imagine pointers at both ends of the remaining portion of the list (excluding the number currently being considered).
Add the numbers pointed to by the two pointers. If the sum equals the negative of the current number, then we have found a valid triplet. Record this triplet.
If the sum is less than the negative of the current number, shift the left pointer one position to the right, seeking a larger value.
If the sum is greater than the negative of the current number, shift the right pointer one position to the left, seeking a smaller value.
Repeat the pointer adjustments until the pointers cross each other. If no triplet is found during this process, move on to the next number in the list.
When considering each number, make sure to skip over any duplicate numbers to avoid generating duplicate triplets.
The list of recorded triplets is the result.

Code Implementation

def find_triplets_that_sum_to_zero(numbers):
    numbers.sort()
    triplets = []
    numbers_length = len(numbers)

    for i in range(numbers_length - 2):
        # Avoid duplicates for the first number
        if i > 0 and numbers[i] == numbers[i - 1]:
            continue

        left_pointer = i + 1
        right_pointer = numbers_length - 1

        while left_pointer < right_pointer:
            current_sum = numbers[i] + numbers[left_pointer] + numbers[right_pointer]

            if current_sum == 0:
                triplets.append([numbers[i], numbers[left_pointer], numbers[right_pointer]])

                # Avoid duplicates for the second number
                while left_pointer < right_pointer and numbers[left_pointer] == numbers[left_pointer + 1]:
                    left_pointer += 1

                # Avoid duplicates for the third number
                while left_pointer < right_pointer and numbers[right_pointer] == numbers[right_pointer - 1]:
                    right_pointer -= 1

                left_pointer += 1
                right_pointer -= 1

            elif current_sum < 0:
                left_pointer += 1 # Need a larger sum

            else:
                right_pointer -= 1 # Need a smaller sum

    return triplets

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty list immediately as no triplets can be formed.
Array with less than 3 elements	Return an empty list since a triplet cannot be formed.
Array with all identical numbers (e.g., all zeros)	The solution should handle duplicate values correctly, ensuring only unique triplets are added to the result, and avoiding issues like [0, 0, 0], [0, 0, 0], etc.
Array with many duplicate numbers	The solution must avoid generating duplicate triplets by skipping over consecutive duplicate numbers after sorting the array.
Array with large positive and negative numbers that could potentially lead to integer overflow during summation	Using a language with automatic overflow handling or employing appropriate checks within the summation can prevent potential overflow errors.
Array contains a large number of zeros.	The solution should handle the case where multiple zeros are present in the array, ensuring that triplets containing zeros are identified and duplicates are avoided.
No triplets sum to zero.	The solution should return an empty list if no such triplets exist.
Input array is very large (potential performance bottleneck)	Sorting the array first (O(n log n)) and then using two pointers to find triplets (O(n^2)) ensures an optimal solution with a time complexity of O(n^2).