3.4 Three Sum

3.4.1 Problem Metadata

3.4.2 Description

Given an integer array nums, return all unique triplets [nums[i], nums[j], nums[k]] such that i < j < k and nums[i] + nums[j] + nums[k] = 0. The solution set must not contain duplicate triplets.

Note: This problem is part of the N Sum Family pattern. See the comparison table in the chapter introduction for a comprehensive comparison of all Two Sum, Three Sum, and Four Sum variants.

3.4.3 Examples

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: Only these two triplets sum to zero without duplication.

3.4.4 Constraints

  • 3 <= nums.length <= 3000
  • -10^5 <= nums[i] <= 10^5

3.4.5 Solution - Sort + Two Pointers

3.4.5.1 Walkthrough

This solution uses a Sort + Two Pointers approach to find all unique triplets that sum to zero.

Core Strategy:

  1. Sort the array to enable the two-pointer technique and group duplicates together
  2. Fix one element (nums[i]) as the first element of each triplet
  3. Use two pointers (left and right) to find pairs in the remaining sorted array that sum to -nums[i]
  4. Skip duplicates at all three positions (i, left, right) to ensure unique triplets

Step-by-step execution:

  1. Sort nums in ascending order
  2. Outer loop: iterate i from 0 to n-3
    • Skip i if nums[i] == nums[i-1] (avoids duplicate triplets with same first element)
    • Initialize left = i + 1, right = n - 1
  3. Inner two-pointer loop while left < right:
    • Calculate sum = nums[i] + nums[left] + nums[right]
    • If sum == 0: Found valid triplet!
      • Add [nums[i], nums[left], nums[right]] to result
      • Move both pointers past all duplicate values
    • If sum < 0: Need larger sum → increment left
    • If sum > 0: Need smaller sum → decrement right

Why Sorting Enables This Solution:

  • Allows two-pointer technique (move left to increase sum, move right to decrease sum)
  • Groups duplicate values together for efficient skipping
  • Maintains sorted order in output triplets automatically

Duplicate Handling (Critical for correctness):

  • First element duplicates: Skip if i > 0 && nums[i] == nums[i-1]
  • Pointer duplicates: After finding a match, move both left and right past all duplicate values to avoid generating the same triplet again

3.4.5.2 Analysis

  • Time Complexity: \(O(n^2)\)
    • Sorting: \(O(n \log n)\)
    • Outer loop: \(O(n)\) iterations
    • Inner two-pointer scan: \(O(n)\) per iteration
    • Overall: \(O(n \log n) + O(n^2) = O(n^2)\) (dominated by nested loops)
  • Space Complexity: \(O(1)\) auxiliary (ignoring the output lc-list)
    • Only uses a few variables for pointers and temporary storage
    • This is optimal for the 3Sum problem

3.4.5.3 Implementation Steps

  1. Sort nums in ascending order using Arrays.sort()
  2. Initialize empty result lc-list
  3. Outer loop: for each index i from 0 to n - 3:
    1. Skip duplicates at position i: If i > 0 and nums[i] == nums[i - 1], continue to next iteration
    2. Initialize two pointers: left = i + 1, right = n - 1
    3. Inner loop: while left < right:
      • Calculate sum = nums[i] + nums[left] + nums[right]
      • Case 1 - Found match (sum == 0):
        • Add triplet [nums[i], nums[left], nums[right]] to result
        • Store current values: leftVal = nums[left], rightVal = nums[right]
        • Move left forward while nums[left] == leftVal (skip left duplicates)
        • Move right backward while nums[right] == rightVal (skip right duplicates)
      • Case 2 - Sum too small (sum < 0):
        • Increment left to increase sum
      • Case 3 - Sum too large (sum > 0):
        • Decrement right to decrease sum
  4. Return result lc-list containing all unique triplets

3.4.5.4 Code - Java

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

        for(int i = 0; i < (len - 2); i++) {
            // skip first duplicates
            if( i> 0 && nums[i] == nums[i-1] ) {
                continue;
            }

            int l = i + 1;
            int r = len - 1;

            while(l < r) {
                int sum = nums[i] + nums[l] + nums[r];

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

                    int lVal = nums[l];
                    int rVal = nums[r];

                    // move left pointer past duplicates
                    while(l < r && nums[l] == lVal) {
                        l++;
                    }

                    // move right pointer past duplicates
                    while(l < r && nums[r] == rVal) {
                        r--;
                    }

                } else if(sum < 0) {
                    // move left pointer forward
                    l++;
                } else { //sum > 0
                    // move right pointer backward
                    r--;
                }
            }

        }

        return result;
    }
}