Three Sum - LeetCode Problem

Problem Description

The problem 3Sum is 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.

Example:

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

Solution

To solve the problem, we follow the steps below:

1. We sort the array using nums.sort().

2. We iterate over each element in the array using a for loop.

3. Inside the loop, we check if the current element is a positive integer or not. If it is, we break out of the loop.

4. If the current element is not a positive integer, we check if it is a duplicate of the previous element. If it is, we skip it using the continue statement. If it is not, we initialize two variables l and r. l will point to the next element after the current element, and r will point to the last element in the array.

5. We then use a while loop which will continue until l is less than r. Inside the while loop, we calculate the sum of the current element, lth element, and rth element. If the sum is greater than 0, we decrement r using r -= 1. If it is less than 0, we increment l using l += 1. If it is equal to 0, we append the triplet to the result and increment l and decrement r using l += 1 and r -= 1. We then check if the next element after l is a duplicate of the current element. If it is, we skip it using the while loop.

6. Finally, we return the result using return res.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()

        for i, a in enumerate(nums):
            # Skip positive integers
            if a > 0:
                break

            if i > 0 and a == nums[i - 1]:
                continue

            l, r = i + 1, len(nums) - 1
            while l < r:
                threeSum = a + nums[l] + nums[r]
                if threeSum > 0:
                    r -= 1
                elif threeSum < 0:
                    l += 1
                else:
                    res.append([a, nums[l], nums[r]])
                    l += 1
                    r -= 1
                    while nums[l] == nums[l - 1] and l < r:
                        l += 1
        return res

Complexity Analysis

The time complexity of this algorithm is O(n^2). This is because we are using nested loops to iterate over the array. The space complexity of this algorithm is O(1), since we are not using any extra space.

Conclusion

In this blog post, we have solved the LeetCode problem "3Sum" using Python. We have explained the solution step-by-step and provided a complexity analysis. Happy Coding!😎