3Sum in Python

The 3Sum problem is a classic algorithmic challenge often encountered in coding interviews and competitions. It involves finding all unique triplets in an array that add up to zero. In this guide, we'll explore the 3Sum problem with a clear problem statement, a step-by-step solution, the full Python code, an explanation of the code, and a discussion of its efficiency.

Problem statement

Given an array nums of n integers, find all unique triplets (a, b, c) in the array such that a + b + c = 0.

Sample input

1nums = [-1, 0, 1, 2, -1, -4]

Sample output

1output = [[-1, -1, 2], [-1, 0, 1]]

Idea to solve

To solve the 3Sum problem, we can use a combination of sorting and the two-pointer technique:

• Sort the Array: First, sort the array to make it easier to avoid duplicates and use the two-pointer technique.
• Iterate through the Array: Use a for loop to iterate through the array. For each element, treat it as the first element of the triplet and use two pointers to find the other two elements.
• Two Pointers: Set two pointers, one at the element immediately after the current element and one at the end of the array. Move the pointers towards each other based on the sum of the three elements.
• Avoid Duplicates: Skip duplicate elements to ensure all triplets are unique.

Full code

Here's the complete Python code to solve the 3Sum problem:

1def three_sum(nums):
2    nums.sort()
3    result = []
4    
5    for i in range(len(nums) - 2):
6        # Skip duplicate elements
7        if i > 0 and nums[i] == nums[i - 1]:
8            continue
9        
10        left, right = i + 1, len(nums) - 1
11        
12        while left < right:
13            total = nums[i] + nums[left] + nums[right]
14            
15            if total < 0:
16                left += 1
17            elif total > 0:
18                right -= 1
19            else:
20                result.append([nums[i], nums[left], nums[right]])
21                
22                # Skip duplicates
23                while left < right and nums[left] == nums[left + 1]:
24                    left += 1
25                while left < right and nums[right] == nums[right - 1]:
26                    right -= 1
27                
28                left += 1
29                right -= 1
30    
31    return result
32
33# Sample input
34nums = [-1, 0, 1, 2, -1, -4]
35# Calling the function and printing the result
36output = three_sum(nums)
37print("3Sum result:", output)

Explanation of the code

• Sort the Array: nums.sort() sorts the array in ascending order.
• Iterate through the Array: We use a for loop to iterate through the array. The loop runs until len(nums) - 2 to ensure there are at least three elements left.
• Skip Duplicates: If the current element is the same as the previous one, we skip it to avoid duplicates.
• Two Pointers: We set left to the element immediately after the current element and right to the last element of the array.
• Calculate the Sum: We calculate the sum of the current element, the left pointer, and the right pointer. If the sum is less than zero, we move the left pointer to the right to increase the sum. If the sum is greater than zero, we move the right pointer to the left to decrease the sum. If the sum is zero, we add the triplet to the result list and move both pointers to skip duplicates.
• Return the Result: After iterating through the array, we return the result list containing all unique triplets.

Time complexity

The time complexity of this approach is O(n^2), where n is the length of the array. This is because we sort the array and then use a nested loop to find the triplets. The space complexity is O(1) for the extra space used by the two pointers, excluding the space required for the output list.