DEV Community

Abhishek Chaudhary
Abhishek Chaudhary

Posted on

3Sum

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 1:

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

Example 2:

Input: nums = []
Output: []

Example 3:

Input: nums = [0]
Output: []

Constraints:

  • 0 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

SOLUTION:

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        if n < 3:
            return []
        triplets = set()
        nums.sort()
        for i in range(n - 2):
            a = nums[i]
            start = i + 1
            end = n - 1
            while start < end:
                b = nums[start]
                c = nums[end]
                total = a + b + c
                if total == 0:
                    triplets.add(tuple(sorted([a, b, c])))
                    start += 1
                    end -= 1
                elif total > 0:
                    end -= 1
                else:
                    start += 1
        return [list(triplet) for triplet in triplets]
Enter fullscreen mode Exit fullscreen mode

Top comments (0)