3Sum LeetCode Problem 15 [Python Solution]

The LeetCode problem known as 3Sum is about exploring efficient approaches to find unique triplets in an array that sum to zero while avoiding duplicates.

Let’s dive in and unravel the secrets to solving this fascinating problem.

Question

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.

Problem Overview

The 3Sum LeetCode problem is a classic algorithmic challenge.

Given an integer array nums, the task is to find all unique triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, j != k, and nums[i] + nums[j] + nums[k] == 0.

It’s important to note that the solution set must not contain duplicate triplets.

Let’s break down the problem and explore a step-by-step approach to solve it efficiently.

Example 1:

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

Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].

Notice that the order of the output and the order of the triplets does not matter.

Example 2:

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

Explanation: The only possible triplet does not sum up to 0.

Example 3:

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

Explanation: The only possible triplet sums up to 0.

Constraints:

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

Understanding the Constraints

Before diving into the solution, let’s understand the constraints of the problem:

The input array nums can contain between 3 and 3000 integers.
Each integer in the array can range from -10^5 to 10^5.
The solution should not contain duplicate triplets, which means that even if there are multiple occurrences of the same triplet, it should only be counted once.

3Sum LeetCode Problem Solution

1. Bruteforce Approach

One way to approach this problem is to use a brute-force solution, which involves trying all possible combinations of three numbers from the array and checking if they sum up to zero.

However, this approach has a time complexity of O(n^3), which is not efficient enough for large inputs.

2. Efficiently Solving 3Sum LeetCode Problem with Two Pointers

To solve this problem efficiently, we can follow these steps:

Sort the input array nums in ascending order. Sorting is a crucial step, as it allows us to eliminate duplicates efficiently.
Iterate through the array using a loop, considering each number as a potential first element of the triplet (let’s call it a).
Inside the loop, use two pointers (left and right) to find the remaining two elements of the triplet that sum to zero. Initially, set left to the next element after a, and right to the last element of the array.
Check the sum of the current triplet (a + nums[left] + nums[right]):
- If the sum is greater than zero, decrement right to decrease the sum.
- If the sum is less than zero, increment left to increase the sum.
- If the sum is zero, add the triplet [a, nums[left], nums[right]] to the result.
While moving the pointers (left and right), make sure to skip duplicate values to avoid duplicate triplets.
Continue this process until the first element of the triplet (a) has been considered for all unique values in the array.

Python Code Solution

Now, let’s implement the efficient approach in Python code:

View on GitHub ➹

def threeSum(self, nums: List[int]) -> List[List[int]]:

    # Sort the input array
    nums.sort()
    result = []
    
    # Iterate through the array
    for i in range(len(nums) - 2):
        # Skip duplicates
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        # Initialize two pointers
        left, right = i + 1, len(nums) - 1
        
        while left &lt; right:
            three_sum = nums[i] + nums[left] + nums[right]
            
            if three_sum > 0:
                right -= 1
            elif three_sum &lt; 0:
                left += 1
            else:
                # Found a triplet
                result.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                
                # Skip duplicates
                while left &lt; right and nums[left] == nums[left - 1]:
                    left += 1
                while left &lt; right and nums[right] == nums[right + 1]:
                    right -= 1
    
    return result

Time and Space Complexity

The time complexity of this efficient solution is O(n^2), where n is the length of the input array nums.

This is significantly more efficient than the brute force approach.

The space complexity is O(1) because we are not using any additional data structures that grow with the input size.

We are only using a constant amount of extra space to store the result.

Reasoning Behind Our Approach

The key insight behind this approach is to sort the input array and use two pointers to efficiently find triplets that sum to zero.

Sorting helps us eliminate duplicates and simplifies the process of finding valid triplets.

By iterating through the array and carefully managing the pointers, we can ensure that we find all unique triplets without unnecessary duplicates.

In summary, this approach leverages the sorted nature of the input array to optimize the search for triplets, resulting in a time-efficient solution.

Conclusion

Solving the 3Sum LeetCode problem requires a careful approach to efficiently find unique triplets that sum to zero in a given array.

By sorting the array and using two pointers, we can significantly reduce the time complexity of the solution from O(n^3) to O(n^2), making it suitable for larger inputs.

Understanding the problem constraints, implementing an efficient approach, and managing duplicates are key aspects of successfully solving this problem.

Solve on LeetCode now.

It’s important to practice and explore similar algorithmic challenges to improve your problem-solving skills in the world of coding and programming.