Skip to content

15. 3SumΒΆ

Problem Link

This problem is similar to Two Sum, we can just use an outer iteration to reduce it to a two sum. The crux of the problem is, how you'd avoid duplicate triplets in result?

One approach could be by sorting the array, and since duplicate values would be adjacent we could directly skip them during each iteration. Also, sorting the array (\(O(nlogn)\)) wouldn't impact the total runtime as loops themselves use \(O(n^2)\).

Pseudocode
  • Sort the input Array and start an outer loop as an indicative of first number in triplet.
  • Skip the number if it's same as previous number, as we've already solved for it and don't want duplicate.
  • Within inner loop since the array is sorted, you can use similar approach as Two Sum 2.
Runtime Complexity

Time: \(O(n^2)\), from two loops.

Space: \(O(1)\)/\(O(n)\), depending on sorting algorithm

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result = []
        nums.sort()
        for i in range(len(nums)):
            if i>0 and nums[i] == nums[i-1]:
                continue
            j, k = i+1, len(nums)-1
            while j < k:
                currSum = nums[i]+nums[j]+nums[k]
                if currSum > 0:
                    k-=1
                elif currSum < 0:
                    j+=1
                else:
                    result.append([nums[i], nums[j], nums[k]])
                    j+=1
                    while j < k and nums[j] == nums[j-1]:
                        j+=1
        return result

func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    var result [][]int
    for i := range nums {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        j, k := i+1, len(nums)-1
        for j < k {
            currSum := nums[i] + nums[j] + nums[k]
            if currSum > 0 {
                k--
            } else if currSum < 0 {
                j++
            } else {
                result = append(result, []int{nums[i], nums[j], nums[k]})
                j++
                for j < k && nums[j] == nums[j-1] {
                    j++
                }
            }
        }
    }
    return result
}