3Sum medium

Problem Statement

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.

Notice that the solution set must not contain duplicate triplets.

Example 1

Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] Explanation: Because [-1,-1,2] and [-1,0,1] are the only two triplets that sum to zero.

Example 2

Input: nums = [0,1,1] Output: [] Explanation: There are no triplets that sum to zero.

Steps

1. Sort the array: Sorting allows us to efficiently handle duplicates and skip unnecessary combinations.

2. Iterate through the array: We'll use a three-pointer approach. The outer loop ( i) iterates from the beginning of the array.

3. Two-pointer approach (inner loop): For each nums[i], we use two pointers, left and right, to scan the remaining array. left starts at i + 1, and right starts at the end of the array (nums.length - 1).

4. Sum calculation: We calculate the sum nums[i] + nums[left] + nums[right].

5. Handling the sum:

   • If the sum is 0, we've found a triplet. We add it to the result list, but only if it's not a duplicate (we'll explain duplicate handling below). Then, we adjust left and right to find other potential triplets.

   • If the sum is less than 0, we need a larger sum, so we increment left.

   • If the sum is greater than 0, we need a smaller sum, so we decrement right.

6. Duplicate handling: To avoid duplicate triplets, we skip over consecutive duplicate elements. When we find a triplet that sums to 0, before adding it to our result, we increment left and decrement right until we encounter unique elements.

Explanation

The key to solving this problem efficiently is the combination of sorting and the two-pointer technique. Sorting allows us to easily identify and skip duplicate elements, preventing duplicate triplets in the result. The two-pointer approach allows us to check all possible pairs in the remaining portion of the array for each nums[i] in O(n) time. This significantly improves upon a brute-force approach which would take O(n^3) time.

Code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

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

        for (int i = 0; i < nums.length - 2; i++) {
            // Skip duplicate elements for nums[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]));
                    // Skip duplicate elements for nums[left] and 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;
    }
}

Complexity

• Time Complexity: O(n^2), due to the nested loops. The sorting step takes O(n log n), but it's dominated by the nested loops.
• Space Complexity: O(log n) in the best case (in-place sorting) or O(n) in the worst case (for sorting in some implementations), plus O(m) to store the result, where m is the number of triplets found. In most cases, m will be smaller than n.