3 sum

Dec 18, 2024 • 5 mins read
Hero Image

Problem Overview

The LeetCode problem "3Sum" is a classic algorithmic challenge involving the sorting and manipulation of arrays that requires finding unique triplets in an array that sum up to zero. It is under the category of two-pointer technique and sorting.

Link to the problem: 3Sum

Problem Description

You are given an integer array nums. The task is to find all the unique triplets (nums[i], nums[j], nums[k]) such that:

  • (i \neq j), (i \neq k), and (j \neq k),
  • (nums[i] + nums[j] + nums[k] = 0).

The solution must not contain duplicate triplets.

Understanding the Problem

Given an integer array, the problem requires identifying all unique triplets that sum up to zero. This is a classic problem in computer science that involves using efficient algorithms to handle the complexity of multiple indices and the prevention of duplicates.

Example

Input:

nums = [-1, 0, 1, 2, -1, -4]

Output:

[[-1, -1, 2], [-1, 0, 1]]

Explanation:

In this example, the array [-1, 0, 1, 2, -1, -4] contains two unique triplets [-1, -1, 2] and [-1, 0, 1] that sum to zero.

Key DSA Concepts and Theory

Two-Pointer Technique

The two-pointer technique is a common strategy used in various algorithm problems where two indices begin from each end of a sorted array and work towards the center. This is particularly useful in problems involving sorted arrays and can significantly reduce the time complexity from quadratic to linear time, especially useful for searching and pair problems.

Sorting

Sorting is a crucial pre-processing step that allows the two-pointer technique to function properly. In this problem, sorting the array enables efficient scanning for combinations without duplication and reduces the complexity of checking each possible triplet in an unsorted array.

Complexity of the Problem

The naive approach to solve the problem by checking every combination is (\mathcal{O}(n^3)), which becomes inefficient for larger arrays. Sorting the array reduces the problem to (\mathcal{O}(n^2)) complexity, which is manageable for typical input sizes.

Solution Approach

Here is a step-by-step breakdown of how to solve the 3Sum problem using sorting and the two-pointer approach:

  1. Sort the array: This enables efficient duplicate checking and simplifies checking the combinations.

  2. Iterate through the array with one pointer: This will serve as the base of our triplet.

  3. Use two pointers to find pairs: For each base element, use the two-pointer technique to find two additional elements that sum to the negation of the base, hence balancing out to zero.

  4. Skip duplicates: Ensure that duplicates are skipped by checking adjacent elements.

C++ Solution

#include <vector>
#include <algorithm>

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

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

        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]});
                // Skip duplicate elements
                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 Solution

import java.util.*;

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

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

            int left = i + 1, 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]));
                    // Skip duplicate elements
                    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;
    }
}

Time and Space Complexity Analysis

Time Complexity

The time complexity of the solution is (\mathcal{O}(n^2)):

  • Sorting takes (\mathcal{O}(n \log n)).
  • The two-pointer search takes (\mathcal{O}(n^2)) in the worst-case scenario.

While the sorting step ((\mathcal{O}(n \log n))) can be costly, the two-pointer method ensures checking for triplets remains efficient.

Space Complexity

The space complexity is (\mathcal{O}(1)) excluding the input and the output list (no additional data structures are used aside from the input list itself).

Common Mistakes to Avoid

  1. Ignoring Duplicate Elements: Failing to skip duplicates can lead to redundant results.

  2. Incorrect Index Handling: Always make sure to reset the left and right pointers correctly and handle index bounds carefully.

  3. Edge Cases: Consider edge cases such as having less than three elements, sorted arrays with same numbers, or arrays with results where all numbers are zero.

Similar Problems on LeetCode

  1. 4Sum - LeetCode 18
  2. Two Sum - LeetCode 1
  3. 3Sum Closest - LeetCode 16

Additional Resources and References

By understanding and applying the two-pointer technique and sorting methodically, you'll successfully implement an efficient solution to the 3Sum problem.