3Sum

Difficulty: Medium

Problem

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

Example

Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
Explanation: The distinct triplets that sum to 0.

Brute-force approach

Check every combination of three elements using three nested loops.

Steps

1. Three nested loops: i, j, k
2. Check if nums[i] + nums[j] + nums[k] = 0
3. Store unique triplets
4. Handle duplicates with a Set

Time complexity: O(n³) · Space complexity: O(k)

Trade-offs

• Three nested loops is very slow O(n³)
• Need extra Set to handle duplicates
• Not suitable for interviews or large inputs

Optimal approach

Key insight: Sort first, then for each fixed element, solve 2Sum with two pointers. Skip duplicates to avoid repeated triplets.

Sort array, fix one element, use two pointers for remaining two.

Steps

1. Sort the array
2. Fix first element at index i
3. Use left = i+1, right = n-1 pointers
4. If sum < 0, move left right. If sum > 0, move right left
5. Skip duplicate values to avoid duplicate triplets

Time complexity: O(n²) · Space complexity: O(1)