Algorithm-Day06-3Sum-lc#15

Posted on In , Views:

🧩 Problem Description

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j != k and nums[i] + nums[j] + nums[k] == 0.

Note: The solution must not contain duplicate triplets.

Example:

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

💡 Brute Force (Too Slow)

Try all triplets (i, j, k) and check if the sum is 0.

  • Time complexity is O(n³)
  • May also return duplicate triplets
  • ❌ Not acceptable for large input sizes

💡 Optimal Approach (Two Pointers After Sorting)

  1. Sort the array
  2. Fix one element nums[i]
  3. Use two pointers left and right to find pairs that sum to -nums[i]
  4. Skip duplicates to ensure unique triplets

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);  // Sort first
        List<List<Integer>> res = new ArrayList<>();

        for (int i = 0; i < nums.length - 2; i++) {
            // Skip duplicates for the first element
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int left = i + 1;
            int right = nums.length - 1;
            int target = -nums[i];

            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum == target) {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    // Skip duplicates 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 < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }

        return res;
    }
}

⏱ Time and Space Complexity

  • Time Complexity: O(n²)
    • Outer loop O(n), inner loop O(n)
  • Space Complexity: O(1) (excluding the output list)

✍️ Summary

  • A classic example of combining sorting + two pointers
  • Always handle duplicates carefully when problems ask for “unique” results
  • This technique is often reused in 4Sum, Two Sum II, etc.

Understanding this pattern gives you a powerful tool for many array + sum problems.