2. Three Sum — Solution Leetcode 15 (Medium) in Python

https://leetcode.com/problems/3sum/description/

Topics: Array, Two Pointers, and Sorting

Companies: Goldman Sachs, Apple, Cisco, and many more..

Problem Description

Solution

“Now, let’s jump into the heart of the article — the solution! We’ll explore the intuition behind the approach, the step-by-step methodology, and finally, the Python code that solves the Three Sum problem.”

#Intuition

The core intuition behind our approach lies in leveraging the ordered nature of a sorted array. Sorting the array brings a sense of structure, allowing us to efficiently explore potential triplets.

# Approach

• Sorting for Order: Sorting the array brings order to the numbers. It allows us to easily identify triplets with a sum of zero, as it creates a situation where small numbers are on one end, and large numbers are on the other.
• Two Pointers for Efficiency: The use of two pointers (let’s call them left and right) is key to efficiently exploring the array. Starting with the smallest and largest numbers, these pointers gradually move toward each other, allowing us to explore different combinations.
• Exploration and Adjustment: As the pointers traverse the array, the sum of the current triplet is calculated. If the sum is greater than zero, it means we need to make the sum smaller, so we move the right pointer to a smaller number. If the sum is less than zero, we need to make the sum bigger, so we move the left pointer to a larger number.
• Identifying Zero Sum Triplets: When the sum is exactly zero, we have found a triplet! This triplet is added to the result, and both pointers move to explore other potential triplets.
• Avoiding Duplicates: To ensure we don’t count duplicate triplets, we use a set to store the unique combinations. This helps maintain the uniqueness of the result.
• Efficient Exploration: The combination of sorting and two-pointer traversal optimizes the exploration of the array. It avoids redundant checks and zeroes in on potential triplets efficiently.

# Complexity

Complexity Analysis: Efficiency matters, and understanding the time and space complexity of our solution is crucial.

• Time Complexity: Sorting the array takes O(n log n) time, where ’n’ is the size of the array. The subsequent two-pointer traversal is linear, taking O(n) time. Therefore, the overall time complexity is O(n log n + n), which simplifies to O(n log n).
• Space Complexity: The algorithm uses a set to store unique triplets, resulting in O(1) space for each triplet and O(k) space overall, where ‘k’ is the number of unique triplets.

# Code

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        triplets=set()
        n=len(nums)
        for i in range(n):
            l=i+1
            r=n-1
            while l<r:
                curr_sum=nums[i]+nums[l]+nums[r]
                if curr_sum>0:
                    r-=1
                elif curr_sum<0:
                    l+=1
                else:
                    triplets.add((nums[i],nums[l],nums[r]))
                    l+=1
                    r-=1
        return triplets

Remember, consistency is the key to mastering coding challenges. Happy coding, Coders !!