3 Sum Problem in DSA (Example and Optimized Solution)

Nidhi Sharma
23h
2.8k
0
0

Article

Introduction

The 3 Sum Problem is a very popular DSA interview question and is a natural extension of the Two Sum problem. In this problem, you are asked to find three numbers in an array whose sum is equal to zero.

This question helps interviewers understand your knowledge of arrays, sorting, the two-pointer technique, and handling duplicates.

In this article, the 3 Sum problem is explained in simple words, with clear examples and easy-to-follow code.

What is the 3 Sum Problem?

You are given an array of integers. Your task is to find all unique triplets in the array such that the sum of the three numbers is zero.

Important points to remember:

The triplets must be unique
The order of numbers inside a triplet does not matter

Example

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

Explanation

The two triplets whose sum is zero are:

(-1) + (-1) + 2 = 0
(-1) + 0 + 1 = 0

Brute Force Approach (Easy but Slow)

The simplest way to solve the 3 Sum problem is to use three nested loops and check all possible triplets.

How it works

Pick the first number
Pick the second number
Pick the third number
Check if their sum is zero

Drawbacks

Time Complexity becomes O(n³)
Very slow for large arrays

Because of this, brute force is not suitable for interviews.

Optimized Approach Using Sorting and Two Pointers

The most efficient and commonly used approach for 3 Sum is:

Sort the array
Fix one element
Use two pointers to find the remaining two numbers

This reduces unnecessary checks and improves performance.

Step-by-Step Explanation

Let us understand the logic clearly.

Steps:

Sort the array
Loop through the array and fix one element at a time
For the fixed element, use two pointers:
- One pointer starts from the next index
- Another pointer starts from the end
Check the sum of the three numbers
Move pointers based on whether the sum is less than, greater than, or equal to zero
Skip duplicate values to avoid repeated triplets

Dry Run Example

Sorted array: [-4, -1, -1, 0, 1, 2]

Fix first element = -1

Left	Right	Sum	Action
-1	2	0	Triplet found
0	1	0	Triplet found

Both valid triplets are stored and duplicates are skipped.

Code Implementation

C++ Code

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> result;
    sort(nums.begin(), nums.end());

    for (int i = 0; i < nums.size(); i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;

        int left = i + 1;
        int right = nums.size() - 1;

        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];

            if (sum == 0) {
                result.push_back({nums[i], nums[left], nums[right]});

                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;

                left++;
                right--;
            }
            else if (sum < 0) {
                left++;
            }
            else {
                right--;
            }
        }
    }
    return result;
}

Java Code

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);

    for (int i = 0; i < nums.length; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;

        int left = i + 1;
        int right = nums.length - 1;

        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];

            if (sum == 0) {
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));

                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;

                left++;
                right--;
            }
            else if (sum < 0) {
                left++;
            }
            else {
                right--;
            }
        }
    }
    return result;
}

Python Code

def threeSum(nums):
    nums.sort()
    result = []

    for i in range(len(nums)):
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left, right = i + 1, len(nums) - 1

        while left < right:
            total = nums[i] + nums[left] + nums[right]

            if total == 0:
                result.append([nums[i], nums[left], nums[right]])

                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1

                left += 1
                right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1

    return result

Time and Space Complexity

Time Complexity: O(n²)
Space Complexity: O(1) (excluding output list)

This is the most optimized and accepted solution for the 3 Sum problem.

Edge Cases to Consider

Array size less than 3
All elements are zero
Large negative or positive values
Duplicate numbers in the array

Handling duplicates correctly is very important.

Common Interview Variations of 3 Sum

3 Sum closest to target
Count number of triplets
3 Sum in sorted array
K Sum problem (general version of 3 Sum)

Summary

The 3 Sum Problem is an important DSA question that builds on sorting and the two pointer technique. By sorting the array and carefully moving pointers while skipping duplicates, you can find all valid triplets efficiently. Understanding this problem helps you solve advanced problems like 4 Sum and K Sum and prepares you well for technical interviews.