Problem Statement

Given an integer array nums, return all unique triplets [nums[i], nums[j], nums[k]] such that:

• i != j, i != k, and j != k
• nums[i] + nums[j] + nums[k] == 0

The solution set must not contain duplicate triplets.

Example:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

---

Intuition

We need to find all unique triplets that sum up to zero.
A brute-force approach would try all possible triplets (O(n³)), but we can do much better using sorting and the two-pointer technique.

---

Optimized Approach: Sorting + Two Pointers

Step-by-step logic:

1. Sort the array first.
   This allows us to use two pointers and easily skip duplicates.
2. Iterate over the array with index i. For each element nums[i], we’ll try to find two other numbers that sum up to -nums[i].
3. Use two pointers:
   • left = i + 1
   • right = n - 1
     Move these pointers based on the sum.
4. Skip duplicate elements for both i, left, and right.

---

Java Solution

import java.util.*;

public class Solution {
    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++) {
            // Skip duplicate values for 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(Arrays.asList(nums[i], nums[left], nums[right]));
                    
                    // Skip duplicates for left and 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++;  // Need larger sum
                } else {
                    right--; // Need smaller sum
                }
            }
        }
        return result;
    }
}

---

Complexity Analysis

• Time Complexity: O(n²)
  Sorting takes O(n log n), and the two-pointer scan takes O(n²) in total.
• Space Complexity: O(1) (ignoring the result list).

---

Dry Run

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

Step 1: Sort array → [-4, -1, -1, 0, 1, 2]

Now iterate:

i	nums[i]	left	right	Sum	Action
0	-4	1	5	-3	Sum < 0 → left++
0	-4	2	5	-3	left++
0	-4	3	5	-2	left++
0	-4	4	5	-1	left++ → exit inner loop
1	-1	2	5	0	Found triplet [-1, -1, 2]
	-1	3	4	0	Found triplet [-1, 0, 1]
2	-1 (duplicate)	skip
3	0	4	5	3	sum > 0 → right–
	0	4	4	stop

Result: [[-1, -1, 2], [-1, 0, 1]]

---

Key Insights

1. Sorting helps avoid duplicates and enables two-pointer traversal.
2. Always skip duplicates for both i, left, and right pointers to maintain uniqueness.
3. Since the array is sorted, increasing left moves toward a larger number and decreasing right moves toward a smaller number — enabling efficient sum adjustment.