15. 3Sum

Time: O(n^2)

Space: O(n)

Intuition

Brute force is O(n^3) - check every triplet. Sort first: this costs O(n log n) but unlocks the two-pointer technique. With the array sorted, fix one number and reduce the problem to "find a pair summing to its negation" - exactly the Two Sum II pattern, solvable in O(n) with two pointers. Total: O(n^2).

Algorithm

1Sort the array in ascending order.
2Iterate i from 0 to n-3. If nums[i] > 0, break early (no three positives can sum to 0).
3Skip duplicate values of nums[i]: if i > 0 and nums[i] == nums[i-1], continue.
4Set left = i+1, right = n-1. Run two-pointer loop while left < right.
5If sum == 0: record [nums[i], nums[left], nums[right]], skip duplicate lefts and rights, then advance both pointers.
6If sum < 0: left++ (need a larger value). If sum > 0: right-- (need a smaller value).

Example Walkthrough

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

1.i=0, nums[i]=-4. Two pointers: left=1(-1), right=5(2). Sum=-3 < 0 -> left++.
2.left=2(-1), right=5(2). Sum=-3 < 0 -> left++. left=3(0), right=5(2). Sum=-2 < 0 -> left++. Exhaust without match.
3.i=1, nums[i]=-1. left=2(-1), right=5(2). Sum=0 -> record [-1,-1,2]. Skip dups, advance.
4.left=3(0), right=4(1). Sum=0 -> record [-1,0,1].
5.i=2, nums[i]=-1 == nums[1] -> skip (duplicate outer).

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

Common Pitfalls

•Skip outer duplicates with `i > 0 && nums[i] == nums[i-1]` - not `nums[i] == nums[i+1]`.
•After finding a match, also skip inner duplicates on both left and right pointers.
•The early break `if nums[i] > 0 return` only works because the array is sorted.

15.cs

// Approach: Sort the array so duplicates are adjacent and the two-pointer technique is valid.
// For each element nums[i], set left = i+1 and right = n-1 and look for pairs summing to -nums[i].
// If nums[left] + nums[right] == -nums[i], record the triplet and skip all duplicate values on both ends.
// If the sum is too small, advance left; if too large, retreat right.
// Skip duplicate values of nums[i] at the outer loop to avoid repeating triplets in the output.
// Sorting is the key enabler — without it we would need O(n^2) hash-set work with deduplication logic.
// Time: O(n^2) Space: O(n) for result storage

public class Solution
{
    public IList<IList<int>> ThreeSum(int[] nums)
    {
        int n = nums.Length;
        Array.Sort(nums);
        IList<IList<int>> result = new List<IList<int>>();
        for (int i = 0; i < n; i++)
        {
            if (i > 0 && nums[i] == nums[i - 1])
                continue;

            int j = i + 1;
            int k = n - 1;

            while (j < k)
            {
                long sum = nums[j] + nums[k];
                sum += nums[i];
                if (sum < 0)
                    j++;
                else if (sum > 0)
                    k--;
                else
                {
                    IList<int> temp = new List<int>()
                    {
                        nums[i],
                        nums[j],
                        nums[k]
                    };
                    result.Add(temp);
                    j++;
                    k--;

                    while (j < k && nums[j] == nums[j - 1]) 
                        j++;
                    while (j < k && nums[k] == nums[k + 1]) 
                        k--;
                }
            }
        }
        return result;
    }
}

Was this solution helpful?