3Sum Problem in Python

The 3Sum problem in Python is a algorithmic challenge where the goal is to find all unique triplets in an array that sum up to zero. Given an array of integers, you are tasked with identifying all possible combinations of three numbers whose sum is zero. This problem is often asked in coding interviews and is an excellent way to practice your problem-solving skills in Python.

In this blog, we will explore the 3Sum problem solution in Python, discuss the best algorithms to solve it, and focus on optimizing the solution for both time and space complexity. Whether you're a beginner learning about array manipulation or an experienced developer looking to refine your algorithmic skills, this lesson will guide you through the 3Sum problem with detailed explanations and hands-on examples.

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.

Key Points to Solve the 3Sum Problem in Python

• Understand the Problem: The 3Sum problem involves finding all unique triplets in an array that sum up to a specific target value (usually zero). The goal is to identify groups of three numbers that add up to zero, without duplicates.
• Sort the Array: To optimize the solution, sort the input array first. Sorting helps in reducing the problem's complexity by making it easier to find possible triplets.
• Use Two Pointers Approach: After fixing one element, use the two-pointer technique to find the other two elements that, together with the fixed element, sum up to zero. This helps improve the time complexity from O(n^3) to O(n^2).
• Skip Duplicates: When iterating through the array, skip over duplicate numbers to avoid redundant triplets. This ensures that the solution only contains unique triplets.
• Handle Edge Cases: Consider edge cases like arrays with fewer than three elements, arrays with only positive or negative numbers, or arrays containing duplicate values.
• Return All Unique Triplets: The final result should be a list of unique triplets that sum to zero. Make sure to filter out duplicate triplets to avoid incorrect results.
• Time and Space Complexity: The time complexity of an optimal solution is O(n^2) due to the sorting and the two-pointer search. The space complexity is O(1) for the two-pointer approach, but O(n) if storing the result list.