# 1. Problem set - **Goal**: Find all unique triplets $[nums[i], nums[j], nums[k]]$ such that their sum is zero. - **Constraints**: - Indices $i, j, k$ must be distinct. - The output must not contain duplicate triplets (e.g., if `[-1, 0, 1]` is found, `[0, -1, 1]` should not be added). - Array size $n$ can be up to $3000$. - Element values range from $-10^5$ to $10^5$. # 2. Methodology - To efficiently find triplets and avoid duplicates, we sort the array first. - We iterate through the array, fixing one element `i`. For the remaining part of the array to the right of `i`, we use a **Two Pointers** approach to find two numbers that sum to `-nums[i]`. - To prevent duplicates: 1. Skip the same value for the fixed element `i`. 2. After finding a valid triplet, skip the same values for both `left` and `right` pointers. - **Algorithm**: Sorting + Two Pointers. - **Data Structure**: `ArrayList` (for result), `int[]` (input). - **Complexity**: - Time: $O(N^2)$ where $N$ is the number of elements (Sorting is $O(N \log N)$, nested loops are $O(N^2)$). - Space: $O(\log N)$ to $O(N)$ depending on the sorting implementation's auxiliary space. # 3. Solution ```java import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class Solution { /** * Finds all unique triplets that sum to zero. * @param nums Input integer array * @return List of triplets */ public List> threeSum(int[] nums) { List> result = new ArrayList<>(); // 1. Sort the array to use two pointers and easily skip duplicates Arrays.sort(nums); int n = nums.length; for (int i = 0; i < n - 2; i++) { // Optimization: Since the array is sorted, if nums[i] > 0, // the sum of three numbers cannot be 0. if (nums[i] > 0) break; // 2. Skip duplicate values for the first element to avoid duplicate triplets if (i > 0 && nums[i] == nums[i - 1]) continue; // 3. Initialize two pointers for the remaining sub-array int left = i + 1; int right = n - 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (sum == 0) { // Found a valid triplet result.add(Arrays.asList(nums[i], nums[left], nums[right])); // 4. Move pointers and skip duplicate values for second and third elements while (left < right && nums[left] == nums[left + 1]) left++; while (left < right && nums[right] == nums[right - 1]) right--; left++; right--; } else if (sum < 0) { // Sum is too small, move left pointer to increase sum left++; } else { // Sum is too large, move right pointer to decrease sum right--; } } } return result; } } ```