3sum Leetcode Solution in Python

The 3Sum problem on LeetCode challenges us to find all unique triplets in an array whose sum equals zero. This problem involves intricate array manipulation and exploration of different algorithmic approaches. In this article, we will walk through the process of solving it using Brute Force, a Better Solution, and an Optimal Solution.

Problem Statement

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. The solution set must not contain duplicate triplets.

google.com, pub-1688327249268695, DIRECT, f08c47fec0942fa0

Leetcode Problem Link – https://leetcode.com/problems/3sum/description/

Brute Force Approach:

The simplest approach to solving the 3Sum problem is through a brute force method. The idea is to generate all possible triplets and check if their sum equals zero. While this method may work, it is highly inefficient, especially for large input arrays.

def threeSumBruteForce(nums):
    result = []
    nums.sort()
    
    for i in range(len(nums) - 2):
        for j in range(i + 1, len(nums) - 1):
            for k in range(j + 1, len(nums)):
                triplet_sum = nums[i] + nums[j] + nums[k]
                if triplet_sum == 0:
                    result.append([nums[i], nums[j], nums[k]])
    
    return result

The time complexity of this solution is O(n^3), making it impractical for large datasets.

Why is the Brute Force approach inefficient for solving the 3Sum problem?

The Brute Force approach involves generating all possible triplets in the array and checking if their sum equals zero. This leads to a time complexity of O(n^3), making it impractical for large datasets. The algorithm explores redundant combinations, resulting in poor performance.

A Better Solution:

To improve upon the Brute Force approach, we can use a two-pointer technique. By sorting the array, we can efficiently explore combinations without redundant calculations.

def threeSumBetter(nums):
    result = []
    nums.sort()
    
    for i in range(len(nums) - 2):
        left, right = i + 1, len(nums) - 1
        
        while left < right:
            triplet_sum = nums[i] + nums[left] + nums[right]
            
            if triplet_sum == 0:
                result.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1
            elif triplet_sum < 0:
                left += 1
            else:
                right -= 1
    
    return result

This solution has a time complexity of O(n^2), a significant improvement over the brute force method.

How does the Two-Pointer technique improve the solution in the “Better Solution”?

The Two-Pointer technique is employed in the “Better Solution” to improve efficiency. By sorting the array, the algorithm can use two pointers to efficiently explore combinations without redundant calculations. This reduces the time complexity to O(n^2) as opposed to the O(n^3) of the Brute Force approach.

What is the significance of sorting the array in the Two-Pointer solutions?

Sorting the array is crucial for the Two-Pointer solutions as it allows for an organized and efficient exploration of combinations. It enables the algorithm to quickly adjust the pointers based on the comparison of the triplet sum with the target value (zero). Sorting facilitates the identification and skipping of duplicate values, optimizing the overall process.

Optimal Solution:

The optimal solution leverages the two-pointer technique while further optimizing the code.

def threeSumOptimal(nums):
    result = []
    nums.sort()
    
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        left, right = i + 1, len(nums) - 1
        
        while left < right:
            triplet_sum = nums[i] + nums[left] + nums[right]
            
            if triplet_sum == 0:
                result.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1
            elif triplet_sum < 0:
                left += 1
            else:
                right -= 1
    
    return result

This optimal solution retains the O(n^2) time complexity but further avoids duplicate triplets more efficiently.

How does the “Optimal Solution” further enhance the efficiency of the Two-Pointer technique?

The “Optimal Solution” builds upon the Two-Pointer technique by incorporating additional checks to skip duplicate elements efficiently. This includes checks to avoid redundant calculations and ensure that the resulting triplets are unique. The “Optimal Solution” retains the O(n^2) time complexity while minimizing unnecessary computations.

What is the time complexity of the Three-Sum problem’s Optimal Solution?

The Optimal Solution for the 3Sum problem has a time complexity of O(n^2). This is achieved by utilizing the Two-Pointer technique and incorporating optimizations to skip duplicate elements efficiently. The algorithm’s performance is significantly improved compared to the Brute Force approach.

Something you might like: