15. 3Sum

15. 3Sum#

Difficulty: Medium

Link to Problem: To see the 3Sum problem on LeetCode, click here!

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.

Constraints:

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

Solution:#

Here’s a Python function to solve this problem:

def threeSum(nums):
    # Sort the input array in ascending order
    nums.sort()
    triplets = []
    
    for i in range(len(nums) - 2):
        # Skip duplicates to avoid duplicate triplets
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        left, right = i + 1, len(nums) - 1
        
        while left < right:
            # Calculate the total sum of the current triplet
            total = nums[i] + nums[left] + nums[right]
            
            if total == 0:
                # If the total is zero, we found a valid triplet
                triplets.append([nums[i], nums[left], nums[right]])
                
                # Skip duplicates of left and right pointers
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                
                # Move the pointers to the next unique elements
                left += 1
                right -= 1
            elif total < 0:
                # If the total is negative, we need to increase the sum by moving the left pointer to the right
                left += 1
            else:
                # If the total is positive, we need to decrease the sum by moving the right pointer to the left
                right -= 1
    
    return triplets

Explanation:#

It starts by sorting the input array nums in ascending order. Sorting helps in efficiently finding triplets that sum up to zero.
It initializes an empty list triplets to store the unique triplets that meet the given conditions.
The code then iterates through the nums array using a loop with index i. This loop will consider each element of the array as a potential starting point for a triplet.
Inside the loop, it checks for duplicates and skips them. This is done to ensure that the solution set does not contain duplicate triplets. If nums[i] is the same as the previous element nums[i-1], it continues to the next iteration of the loop.
Two pointers, left and right, are initialized. left starts just after the current element nums[i], and right starts at the end of the array.
The code enters another loop with left and right pointers, trying to find a triplet that sums up to zero.
It calculates the total sum of the current triplet as nums[i] + nums[left] + nums[right].
If total is zero, it means a valid triplet is found, so it appends [nums[i], nums[left], nums[right]] to the triplets list. Then, it moves both the left and right pointers to their next unique elements while skipping duplicates.
If total is less than zero, it means the sum is negative, so it increments the left pointer to move towards a larger sum.
If total is greater than zero, it means the sum is positive, so it decrements the right pointer to move towards a smaller sum.
This process continues until all possible triplets have been considered.
Finally, the function returns the triplets list, which contains all the unique triplets that sum up to zero in the sorted nums array.

Test cases#

# Example 1:
nums = [-1, 0, 1, 2, -1, -4]
result = threeSum(nums)
print(result)

[[-1, -1, 2], [-1, 0, 1]]

# Example 2
nums = [0, 1, 1]
result = threeSum(nums)
print(result)

[]

# Example 3
nums = [0, 0, 0]
result = threeSum(nums)
print(result)

[[0, 0, 0]]

Time and Space Complexity Analysis#

Let’s analyze the time and space complexity of the threeSum function:

Time Complexity:

Sorting the input array nums takes O(n log n) time, where n is the length of the array.
The outer loop runs for each element of the array, so it iterates O(n) times.
Inside the outer loop, we have a while loop with two pointers (left and right). In the worst case, the while loop can iterate O(n) times (when all elements are unique).
Inside the while loop, we have constant time operations (additions, comparisons, and list appends).

Overall, the time complexity of the threeSum function is dominated by the sorting step, so it is O(n log n) due to the sorting. The other operations inside the loops contribute linearly but are dominated by the sorting step.

Space Complexity:

The space used by the triplets list to store the output triplets is O(k), where k is the number of unique triplets that sum up to zero. In the worst case, this can be O(n^2/3) because there can be roughly O(n^2) possible triplets, and many of them may sum up to zero.
Other than the triplets list, the function uses only a constant amount of additional space for variables like i, left, right, and total.

Overall, the space complexity of the threeSum function is O(k), where k is the number of unique triplets that meet the criteria. It’s important to note that the space complexity does not depend on the size of the input array but rather on the number of valid triplets found.

In summary:

Time Complexity: O(n log n) due to sorting (dominant factor) and O(n^2) in the worst case for the nested loops.
Space Complexity: O(k) for storing the output triplets, where k is the number of unique triplets that meet the criteria.

Challenging Exercises:#

K-Sum Problem: Generalize the problem to the K-Sum problem, where instead of finding triplets that sum to zero, you need to find K elements that sum to a target value. Implement a function for this generalization.
Count the Number of Unique Triplets: Modify the algorithm to count the number of unique triplets that satisfy the conditions instead of returning the triplets themselves. This will require some modifications to handle duplicates efficiently.