3 Sum

Problem Link

https://leetcode.com/problems/3sum

Problem Statement

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

• i != j, j != k, i != k

• nums[i] + nums[j] + nums[k] == 0

The solution set must not contain duplicate triplets.

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]]

Constraints

• 3 <= nums.length <= 3000

• -10^5 <= nums[i] <= 10^5

Intuition

We want all triplets (i, j, k) such that nums[i] + nums[j] + nums[k] == 0 and no two triplets are identical (regardless of order).

This is efficiently solved by:

• Fixing one element nums[i]

• Searching for two other elements nums[j] + nums[k] == -nums[i] using the two-pointer technique

Sorting is essential to help with both duplicate removal and efficient pair search.

Approach

1. Sort the array.

2. Loop i from 0 to n - 3:

   • Skip duplicate values at nums[i] to avoid duplicate triplets.

   • Set two pointers left = i + 1 and right = n - 1

   • While left < right:

     • Compute sum = nums[i] + nums[left] + nums[right]

     • If the sum is zero, store the triplet and skip duplicate values for both left and right

     • If the sum is less than zero, increment left

     • If the sum is greater than zero, decrement right

Code

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

        for (int i = 0; i < nums.length; i++) {
            if (i == 0 || nums[i] != nums[i - 1]) {
                int target = -nums[i];
                int l = i + 1;
                int r = nums.length - 1;

                while (l < r) {
                    int currSum = nums[l] + nums[r];
                    if (currSum == target) {
                        ans.add(Arrays.asList(nums[i], nums[l], nums[r]));

                        while (l < r && nums[l] == nums[l + 1]) l++;
                        while (l < r && nums[r] == nums[r - 1]) r--;

                        l++;
                        r--;
                    } else if (currSum < target) {
                        l++;
                    } else {
                        r--;
                    }
                }
            }
        }
        return ans;
    }
}

Dry Run

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

i = 0 → nums[i] = -4

• target = 4

• left = 1 (-1), right = 5 (2) → sum = 1 → move left

• left = 2 (-1), right = 5 → sum = 1 → move left

• left = 3 (0), right = 5 → sum = 2 → move left

• left = 4 (1), right = 5 → sum = 3 → move left

i = 1 → nums[i] = -1

• target = 1

• left = 2 (-1), right = 5 (2) → sum = 1 → triplet: [-1, -1, 2]
  skip duplicates, left = 3, right = 4

• left = 3 (0), right = 4 (1) → sum = 1 → triplet: [-1, 0, 1]
  skip duplicates, left = 4, right = 3 → break

i = 2 → nums[i] = -1 (duplicate) → skip

i = 3 → nums[i] = 0

• target = 0

• left = 4 (1), right = 5 (2) → sum = 3 → move right

• left = 4, right = 4 → break

Time and Space Complexity

Conclusion

• Sorting and two-pointer method helps achieve optimal time.

• Proper duplicate checks are crucial to prevent redundant triplets.

• This is a base case of the general k-sum pattern.

Let me know if you want:

• A brute-force cubic solution

• Extension to 4Sum

• Hash-based variant for practice