#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/two-pointers/3sum-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/two-pointers/3sum-implementation

Repovive

3Sum - Implementation - Two Pointers | Fundamental Algorithms | Repovive

Repovive.

Fundamental Algorithms8 sections · 294 units2h total

Open in Course

3Sum - Implementation

Here is the implementation:

function threeSum(nums):
    sort(nums)
    result = []

    for i from 0 to nums.length - 3:
        if i > 0 and nums[i] == nums[i-1]:
            continue

        left = i + 1
        right = nums.length - 1
        target = -nums[i]

        while left < right:
            sum = nums[left] + nums[right]
            if sum == target:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left+1]: left++
                while left < right and nums[right] == nums[right-1]: right--
                left++
                right--
            else if sum < target:
                left++
            else:
                right--

    return result

$O(n^2)$ time, $O(1)$ extra space (excluding output).