10 - 3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] where nums[i] + nums[j] + nums[k] == 0, and the indices i, j and k are all distinct.

The output should not contain any duplicate triplets. You may return the output and the triplets in any order.

Examples¶

Example 1

Input:

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

Output:

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

Example 2

Input:

nums = [0, 1, 1]

Output:

[]

Example 3

Input:

nums = [0, 0, 0]

Output:

[[0, 0, 0]]

Solution¶

Java Code¶

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

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // Step 1: Sort the array to use two-pointer approach and easily handle duplicates
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();

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

            // Step 3: Use two pointers for the remaining part of the array
            int left = i + 1;
            int right = nums.length - 1;

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

                if (sum == 0) {
                    // Triple found!
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    // Step 4: Skip duplicate elements for left and right pointers
                    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 res;
    }
}

Java Collections Framework Components Used¶

1. List & ArrayList¶

What they are¶

List is an interface representing an ordered collection, and ArrayList is its resizable-array implementation.

How they are used¶

List<List<Integer>> res = new ArrayList<>();

2. Arrays.sort()¶

What it is¶

A utility method in the java.util.Arrays class used to sort arrays of primitives or objects. For primitives, it uses a Dual-Pivot Quicksort.

Why it is used¶

Sorting is crucial for: 1. Handling Duplicates: By sorting, identical elements are adjacent, making them easy to skip. 2. Two-Pointer Logic: Allows us to move pointers systematically (left++ to increase sum, right-- to decrease it).

3. Arrays.asList()¶

What it is¶

A factory method that returns a fixed-size list backed by the specified array.

How it is used¶

res.add(Arrays.asList(nums[i], nums[left], nums[right]));

Intuition¶

The problem asks for triplets summing to zero without duplicates. A brute-force \(O(n^3)\) approach would be too slow.

1. Sort the array: This allows us to use the two-pointer technique for a \(O(n^2)\) solution.
2. Fix the first element: Iterate through the array, treating nums[i] as the first member of a potential triplet.
3. Pointers for the rest: For each i, set left = i + 1 and right = length - 1.
4. Avoid Duplicates:
5. Skip nums[i] if it's the same as the previous element.
6. After finding a valid sum, skip duplicates for left and right before moving them again.

Complexity Analysis¶

Time Complexity¶

O(n^2)

Sorting takes \(O(n \log n)\). The main loop runs \(O(n)\) times, and inside it, the two-pointer traversal takes \(O(n)\), resulting in \(O(n^2)\).

Space Complexity¶

O(1) or O(n)

Depends on the implementation of Arrays.sort(). Dual-Pivot Quicksort typically uses \(O(\log n)\) space for the recursion stack. (Excluding the output list).

Key Takeaways¶

• Sort first to simplify duplicate handling and enable two-pointer optimization.
• Skipping adjacent duplicates is the key to uniqueness in the results.
• JCF utilities like Arrays.sort and Arrays.asList drastically reduce boilerplate code.