Data Structures & Algorithms (Two Pointers): Three Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

NOTE: The solution set must not contain duplicate triplets. The order of the output and the order of the triplets does not matter.

Example

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
- nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
- nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
- nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.

The distinct triplets are [-1,0,1] and [-1,-1,2].

Solve Here: Leetcode 15

Design Rationale

The following are the key concepts to consider when designing an efficient algorithm for this problem:

Q. How to make sure no triplets with the same set of numbers are added to the result?

A simple approach is to sort the array. Once sorted, identical triplets will have the same ordered representation. For example:

Before sorting: nums = [-1,0,1,2,-1,-4]
After sorting: nums = [-4,-1,-1,0,1,2]

- nums[1] + nums[3] + nums[4] = (-1) + 0 + 1 = 0
- nums[2] + nums[3] + nums[4] = (-1) + 0 + 1 = 0  <- duplicate triplet

Approach 1: Sorting + Nested Loops

Use three nested loops to iterate through all possible triplets and keep track of the unique ones whose sum is 0.

Algorithm

1. Sort the input array.
Initialize an empty set to store the unique triplets.
3. Iterate through the array using three pointers i, j, and k:
    - For each triplet, check if nums[i] + nums[j] + nums[k] == 0:
        - If the sum is equal to 0, store the triplet to the result set.
4. Convert the result set into list and return it.

Implementation

public List<List<Integer>> threeSum(int[] nums) {
    // 1. Sort the input array
    Arrays.sort(nums);

    // 2. Iterate over the sorted set of triplets
    Set<List<Integer>> resultSet = new HashSet<>();
    for(int i = 0; i < nums.length - 2; i++) {

        // Optimization: Skip duplicates
        if (i > 0 && nums[i] == nums[i - 1]) continue;

        for(int j = i + 1; j < nums.length - 1; j++) {

            // Optimization: Skip duplicates
            if (j > i + 1 && nums[j] == nums[j - 1]) continue;

            for(int k = j + 1; k < nums.length; k++) {

                // Optimization: Skip duplicates
                if (k > j + 1 && nums[k] == nums[k - 1]) continue;

                if (nums[i] + nums[j] + nums[k] == 0) {
                    List<Integer> triplet = List.of(nums[i], nums[j], nums[k]);
                    resultSet.add(triplet);
                }
            }
        }
    }
    
    return new ArrayList<>(resultSet);
}

Time Complexity

Sorting the array takes O(n log n) time. The nested loops take O(n^3) time. Hence, the overall time complexity is O(n^3).

Space Complexity

There are n(n-1)(n-2)/6 ~ O(n³) possible combinations of three elements, but the sum = 0 constraint greatly limits how many of those combinations can actually be valid.

Once we choose two numbers a and b, the third number is completely determined: c = −(a+b). So we don't have O(n) choices for the third element anymore. That's the key reason the number of valid unique triplets is bounded by O(n²).

So the overall space complexity is O(n²).

Approach 2: Sorting + Two Pointers

For every element i, we can use two pointers j and k to find the other two elements such that nums[j] + nums[k] + nums[i] == 0.

Algorithm

1. Sort the input array.
2. Iterate through the array using a pointer i:
    - For each element i, let j = i + 1 and k = nums.length - 1:
        - while j < k:
            - if nums[i] + nums[j] + nums[k] == 0:
                - store the triplet to the result set.
            - else if nums[i] + nums[j] + nums[k] < 0:
                - increment j.
            - else:
                - decrement k.
3. Convert the result set into list and return it.

Implementation

public List<List<Integer>> threeSum(int[] nums) {
    // 1. Sort the input array
    Arrays.sort(nums);

    // 2. Iterate over each element i in the sorted array
    Set<List<Integer>> resultSet = new HashSet<>();
    for(int i = 0; i < nums.length - 2; i++) {
        // Optimization: Skip duplicates
        if (i > 0 && nums[i] == nums[i - 1]) continue;

        int j = i + 1;
        int k = nums.length - 1;
        while (j < k) {
            if (nums[i] + nums[j] + nums[k] == 0) {
                resultSet.add(List.of(nums[i], nums[j], nums[k]));
                j++;
                k--;
            } else if (nums[i] + nums[j] + nums[k] < 0) {
                j++;
            } else {
                k--;
            }
        }
    }

    return new ArrayList<>(resultSet);
}

Time Complexity

Sorting the array takes O(n log n) time. The nested loop perform a linear search through the remaining elements for each i, resulting in O(n²) time. Hence, the overall time complexity is O(n log n) + O(n²) = O(n²).

Space Complexity

There are O(n²) possible combinations of two elements. Hence, the overall space complexity is O(n²).