DKodeTree Small Logo
DKodeTreeWhere logic takes root...!
3Sum - Solution
Solutions and explanations
Link to Problem StatementView on GitHub

This approach uses the concepts of sorting and hash sets to find the unique triplets that sum to zero from an input array:

  • Sort the array.
  • Then, for each element, use a hash set to find pairs that sum to its negative to identify the triplets.
  • Duplicate triplets are avoided through initial sorting, by skipping repeated elements, using a set to ensure uniqueness, and consistently adding triplets in the same positional order.
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        length = len(nums)
        res = set()
        for i in range(length):
            # Skip duplicate first number
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            seen = set()
            for j in range(i + 1, length):
                target = - (nums[i] + nums[j])
                if target in seen:
                    res.add((nums[i], nums[j], target))
                seen.add(nums[j])
        return [[x, y, z] for x, y, z in res]

Complexity Analysis

Here, n is the input size, and k is the number of unique triplets in the result.

  • Time Complexity: O(n²)

    • Sorting the input takes O(n log n) time.

    • The main loop scans through each of the n elements once.

      • For each element, a hash set is used to check for a complement (or target) that completes a triplet summing to zero.
      • This inner scan runs in O(n) time for each element in the outer loop, and set operations (lookup and insert) take O(1) time on average.

      Therefore, the total time complexity of the nested iteration is O(n × n) = O(n²).

    Since O(n²) dominates O(n log n), the overall time complexity is O(n²).

  • Space Complexity: O(n + k)

    • Output space: O(k) for storing the k unique triplets in the result.
    • Sorting Space: O(1) if sorting is done in-place, otherwise, O(n) if additional space is used depending on the sorting implementation.
    • Auxiliary Space: O(n)) for the temporary hash set used during the inner iteration to track complements (or targets).

    Therefore, the total space complexity is the sum of Output Space + Sorting Space + Auxilliary Space, which results in O(n + k).

This approach uses the concepts of sorting and two-pointers to find the unique triplets that sum to zero from an input array:

  • Sort the array.
  • Then, for each index i, use two pointers (left and right) to find pairs such that nums[i] + nums[left] + nums[right] == 0, while skipping duplicates to avoid redundant triplets.
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        length = len(nums)

        res = []
        for i in range(length):
            # Skip duplicates for first number
            if i > 0 and nums[i] == nums[i - 1]:
                continue    

            left, right = i + 1, length - 1
            while left < right:
                cur_sum = nums[i] + nums[left] + nums[right]

                if cur_sum < 0:
                    # Move left and skip duplicates for second number
                    left += 1
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1

                elif cur_sum > 0:
                    # Move right and skip duplicates for the third number
                    right -= 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1

                else:
                    # Found a valid triplet
                    res.append([nums[i], nums[left], nums[right]]) 

                    # Move both pointers and skip duplicates
                    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
        
        return res

Complexity Analysis

Here, n is the input size, and k is the number of unique triplets in the result.

  • Time Complexity: O(n²)
    • Sorting the input takes O(n log n) time.
    • The main loop scans through each of the n elements once. And for each element, the two-pointer scan runs in O(n) time, resulting in an overall O(n²) time for the scanning phase.
    • Since O(n²) dominates O(n log n), the overall time complexity is O(n²).
  • Space Complexity: O(k) or O(n + k)
    • Output space: O(k) for storing the k unique triplets in the result.
    • Sorting Space: O(1) if sorting is done in-place, otherwise, O(n) if additional space is used.
    • So, the total space complexity is Output Space + Sorting Space, which is O(k) or O(n + k), depending on whether implementation of sorting used is in-place or not.