LeetCode Problem 15: 3Sum | Optimal Two-Pointer Approach Explained 🚀

Having trouble with the 3Sum problem on LeetCode? Don’t worry—we’ve got you covered with an efficient and intuitive guide using the two-pointer technique. Learn how to find all unique triplets that sum to zero, avoid duplicates, and impress in coding interviews with clean Java code and deep understanding.

🔍 Problem Statement: 3Sum

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

🧪 Example:

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

💡 Why Use Sorting + Two Pointers?

A brute-force approach would check every triplet using three nested loops → O(n³) time complexity. But with sorting + two pointers, we can bring this down to O(n²) efficiently.

✅ Key Strategy:

1. Sort the array to simplify logic and manage duplicates.
2. Fix one number (nums[i]) and use two pointers (j and k) to find pairs that sum to -nums[i].
3. Avoid duplicates using clever pointer movement or a Set.

✅ Java Solution: Basic Two-Pointer with HashSet

import java.util.*;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> triplets = new ArrayList<>();
        Set<List<Integer>> seen = new HashSet<>();
        int n = nums.length;

        for (int i = 0; i < n - 2; i++) {
            int j = i + 1, k = n - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == 0) {
                    List<Integer> triplet = Arrays.asList(nums[i], nums[j], nums[k]);
                    if (seen.add(triplet)) {
                        triplets.add(triplet);
                    }
                    j++;
                    k--;
                } else if (sum > 0) {
                    k--;
                } else {
                    j++;
                }
            }
        }
        return triplets;
    }
}

📊 Complexity Analysis

🔎 Step-by-Step Breakdown

Step 1: Sort the Array

For example: [-1, 0, 1, 2, -1, -4] → [-4, -1, -1, 0, 1, 2]

Step 2: Loop with Fixed Element i

For each nums[i], use two pointers:

• j = i + 1 (left)
• k = n - 1 (right)

Step 3: Check Triplet Sum

• If sum == 0 → save triplet, move both pointers.
• If sum < 0 → move j right to increase sum.
• If sum > 0 → move k left to decrease sum.

Step 4: Avoid Duplicates

Use a HashSet or skip duplicates using index comparisons.

✅ Optimized Java Version (No HashSet, In-Place Duplicate Skips)

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;

        for (int i = 0; i < n - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue; // Skip duplicate i

            int j = i + 1, k = n - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];

                if (sum == 0) {
                    result.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    j++;
                    k--;

                    while (j < k && nums[j] == nums[j - 1]) j++; // Skip duplicate j
                    while (j < k && nums[k] == nums[k + 1]) k--; // Skip duplicate k

                } else if (sum < 0) {
                    j++;
                } else {
                    k--;
                }
            }
        }
        return result;
    }
}

🔥 Space Complexity Improved: O(1) extra space (excluding output)

❌ Common Mistakes to Avoid

1. Not handling duplicates: Leads to repeated triplets.
2. Using three nested loops: Too slow for large inputs.
3. Skipping pointer movement: Can cause infinite loops or missed answers.
4. Edge Cases:
   • All zeros: [0, 0, 0] → valid triplet
   • Less than 3 numbers: return empty list

🌍 Real-World Use Cases

• Data Reconciliation: Find groups that neutralize each other’s values.
• Financial Systems: Triplet transactions summing to zero.
• Analytics: Detect balanced clusters in datasets.

💼 Why Companies Love This Problem

Top tech companies like Amazon, Google, and Meta love 3Sum because it tests:

• Algorithm design (O(n²) from O(n³))
• Handling edge cases and duplicates
• Writing clean, efficient, readable code

🧠 Similar Problems to Practice

🎯 Conclusion

The 3Sum problem is an essential interview classic that teaches powerful techniques like sorting, two-pointer traversal, and duplicate management.

Master it, and you’ll gain a deep understanding that applies to countless problems in coding interviews and real-world applications.

Ready to level up? Keep exploring our LeetCode solution series and sharpen your algorithmic edge.

Happy coding! 💻🔥