Crack the Backend

Problem Statement

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

"Unique triplets" means no duplicate triplets (e.g. same three values in different order count as one). Sorting the array and skipping duplicate values for the first element and while moving pointers helps avoid duplicates.
The array may contain duplicates; we need to skip over duplicate values when fixing the first element and when moving left/right.

Key Observations

Sort the array. For each index i (as the first element of the triplet), we need two other indices j, k such that nums[j] + nums[k] == -nums[i]. So we reduce to 2Sum on the suffix [i+1..n-1] with target -nums[i], which we can solve with two pointers left = i+1, right = n-1.
To avoid duplicate triplets: (1) If nums[i] == nums[i-1], skip i. (2) When we find a triplet, move left and right past any duplicate values.
Two pointers: if sum < 0, left++; if sum > 0, right--; if sum == 0, record and skip duplicates.

Approach

High-level: Sort nums. For each i (skip if nums[i] == nums[i-1]): set left = i+1, right = n-1, target t = -nums[i]. While left < right: if nums[left] + nums[right] == t, add [nums[i], nums[left], nums[right]], then move left and right past duplicates; else if sum < t, left++; else right--. Return the list of triplets.

Steps:

Arrays.sort(nums). For i = 0..n-3: if i > 0 && nums[i] == nums[i-1], continue. left = i+1, right = n-1, t = -nums[i].
While left < right: sum = nums[left] + nums[right]. If sum == t, add triplet, then left++ and right-- past duplicates. If sum < t, left++; else right--.
Return result.

Implementation

Java

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;
        }

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

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

            if (sum == 0) {
                result.add(List.of(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;
}

Test Cases

Example 1

Input

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

Expected

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

Explanation

Unique triplets that sum to 0.

Complexity Analysis

Time: O(n^2).
Space: O(1) excluding output.

Follow-ups

4Sum: add one more loop and 2Sum.