Table of Contents

The Three Sum problem is a well-known problem in computer science that involves finding all unique triplets in an array of integers that add up to a target sum.

For example, given the array [1, 2, 3, 4, 5, 6, 7] and a target sum of 10, the solution would be [[1, 2, 7], [1, 3, 6], [1, 4, 5], [2, 3, 5]], as these are the unique combinations of three integers that add up to 10.

The pseudocode for solving this problem using a brute-force approach is as follows:

function threeSum(nums, target):
    result = []
    n = length(nums)
    for i from 0 to n-3:
        for j from i+1 to n-2:
            for k from j+1 to n-1:
                if nums[i] + nums[j] + nums[k] == target:
                    triplet = [nums[i], nums[j], nums[k]]
                    triplet.sort()
                    if triplet not in result:
                        result.append(triplet)
    return result

This pseudocode has a time complexity of O(n^3) since it requires three nested loops to iterate over all possible triplets. A more efficient solution can be achieved using a two-pointer approach, which has a time complexity of O(n^2).

there are several efficient approaches to solve the Three Sum problem. I’ll provide pseudocode for two more approaches: one that uses the Two Sum problem as a helper function and another that uses a sorting-based approach.Leetcode 463 Island Perimeter

Approach 2: Two Sum Approach

This approach uses the Two Sum problem as a helper function to solve the Three Sum problem. For each element num in the input array, we use the Two Sum function to find a pair of numbers that add up to target - num.

We add num to the pair to form a triplet that adds up to the target sum. Since the Two Sum function is linear time, this approach has a time complexity of O(n^2).

function threeSum(nums, target):
    result = []
    n = len(nums)
    nums.sort()
    for i from 0 to n-3:
        if i > 0 and nums[i] == nums[i-1]:
            continue
        left = i+1
        right = n-1
        while left < right:
            curr_sum = nums[i] + nums[left] + nums[right]
            if curr_sum == target:
                result.append([nums[i], nums[left], nums[right]])
                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
            elif curr_sum < target:
                left += 1
            else:
                right -= 1
    return result

In this approach, we first sort the input array to make it easier to find duplicates and to use the Two Sum function. We then iterate over the array, skipping duplicates, and for each element, we use the Two Sum function to find a pair of numbers that add up to the target sum minus the current element.

We add the current element to the pair to form a triplet that adds up to the target sum. We also use two pointers to keep track of the left and right ends of the array, and we move them accordingly to find all possible triplets.

Approach 3: Sorting Approach

This approach involves sorting the input array and using two pointers to find all possible triplets that add up to the target sum. We first sort the input array and then iterate over it, skipping duplicates.

For each element num in the array, we use two pointers, one that starts at the next element left and another that starts at the last element right. We then move the pointers inward, checking the sum of the current triplet against the target sum.

If the sum is less than the target sum, we increment the left pointer. If the sum is greater than the target sum, we decrement the right pointer. If the sum is equal to the target sum, we add the triplet to our results and skip any duplicates of left and right.

This approach has a time complexity of O(n^2) since we iterate over the array only once and use two pointers to find all possible triplets.

function threeSum(nums, target):
    result = []
    n = len(nums)
    nums.sort()
    for i from 0 to n-3:
        if i > 0 and nums[i] == nums[i-1]:
            continue
        left = i+1
        right = n-1
        while left < right:
            curr_sum = nums[i] + nums[left] + nums[right]
            if curr_sum == target:
                result.append([nums[i], nums[left], nums[right]])
                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
        elif curr_sum < target:
            left += 1
        else:
            right -= 1
return result

In this approach, we also sort the input array and iterate over it, skipping duplicates. We then use two pointers, `left` and `right`, to move inward from opposite ends of the array.

We compare the sum of the current triplet with the target sum, and move the pointers accordingly to find all possible triplets. We also skip any duplicates of `left` and `right` to avoid adding duplicate triplets to our result.

Both of these approaches are more efficient than the brute-force approach I mentioned earlier, with the sorting-based approach being the most efficient with a time complexity of O(n^2).

The sorting-based approach is better than the Two Sum approach in terms of time complexity. The sorting-based approach has a time complexity of O(n^2) while the Two Sum approach has a time complexity of O(n^2 log n).

This is because the sorting-based approach requires only two nested loops and the use of two pointers, while the Two Sum approach requires the use of the Two Sum function, which itself has a time complexity of O(n log n), and an additional loop.

However, the Two Sum approach is more space-efficient than the sorting-based approach. The Two Sum approach requires only a constant amount of extra space for variables, while the sorting-based approach requires extra space for sorting the input array.

Three Sum : Java Solution

import java.util.*;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int target = -nums[i];
            int left = i + 1;
            int right = n - 1;
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum == target) {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return result;
    }
}

In this Java implementation, we first sort the input array to make it easier to find duplicates and use the Two Sum approach.

We then iterate over the array, skipping duplicates, and for each element num in the array, we use two pointers, one that starts at the next element left and another that starts at the last element right.

We then move the pointers inward, checking the sum of the current triplet against the target sum. If the sum is less than the target sum, we increment the left pointer.

If the sum is greater than the target sum, we decrement the right pointer. If the sum is equal to the target sum, we add the triplet to our results and skip any duplicates of left and right.

Three Sum : JavaScript Solution

var threeSum = function(nums) {
    let result = [];
    nums.sort((a, b) => a - b);
    let n = nums.length;
    for (let i = 0; i < n - 2; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        let target = -nums[i];
        let left = i + 1;
        let right = n - 1;
        while (left < right) {
            let sum = nums[left] + nums[right];
            if (sum === target) {
                result.push([nums[i], nums[left], nums[right]]);
                left++;
                right--;
                while (left < right && nums[left] === nums[left - 1]) left++;
                while (left < right && nums[right] === nums[right + 1]) right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
    return result;
};

In this JavaScript implementation, we also sort the input array and iterate over it, skipping duplicates.

We use two pointers, left and right, to move inward from opposite ends of the array. We compare the sum of the current triplet with the target sum, and move the pointers accordingly to find all possible triplets.

We also skip any duplicates of left and right to avoid adding duplicate triplets to our result.

Three Sum : Python Solution

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result = []
        nums.sort()
        n = len(nums)
        for i in range(n-2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            target = -nums[i]
            left = i+1
            right = n-1
            while left < right:
                curr_sum = nums[left] + nums[right]
                if curr_sum == target:
                    result.append([nums[i], nums[left], nums[right]])
                    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
                elif curr_sum < target:
                    left += 1
                else:
                    right -= 1
        return result

In this Python implementation, we use a similar approach as in the Java and JavaScript implementations.

We sort the input array, iterate over it, and use two pointers to find all possible triplets that add up to the target sum.

We also skip duplicates and move the pointers accordingly to avoid adding duplicate triplets to our result.

Three Sum : Ruby Solution

def three_sum(nums)
    result = []
    nums.sort!
    n = nums.length
    for i in 0..n-3 do
        next if i > 0 && nums[i] == nums[i-1]
        target = -nums[i]
        left = i+1
        right = n-1
        while left < right do
            curr_sum = nums[left] + nums[right]
            if curr_sum == target
                result << [nums[i], nums[left], nums[right]]
                left += 1
                right -= 1
                left += 1 while left < right && nums[left] == nums[left-1]
                right -= 1 while left < right && nums[right] == nums[right+1]
            elsif curr_sum < target
                left += 1
            else
                right -= 1
            end
        end
    end
    result
end

In this Ruby implementation, we also sort the input array and use two pointers to find all possible triplets that add up to the target sum.

We skip duplicates and move the pointers accordingly to avoid adding duplicate triplets to our result.

Written by

With 10+ years in software engineering, I specialize in blogging and web development. My skills span front-end, back-end, database design, web security, and SEO. Passionate about crafting helpful digital experiences.