015. 3Sum

At a Glance

• Topic: Array
• Pattern: Analyze Pattern
• Difficulty: Medium
• LeetCode: 015

Problem Statement

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.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] Explanation: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. The distinct triplets are [-1,0,1] and [-1,-1,2]. Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1] Output: [] Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0] Output: [[0,0,0]] Explanation: The only possible triplet sums up to 0.

Constraints:

3 <= nums.length <= 3000
-105 <= nums[i] <= 105

Approach & Solution Steps

• Three loops are O(n^3). Anchor plus hash set is O(n^2) but dedupe is messy. Sort plus two pointers is the standard O(n^2) solution.

Optimal JS Solution

function threeSum(nums) {
	nums.sort((a, b) => a - b);
	const out = [];

	for (let anchor = 0; anchor < nums.length - 2; anchor++) {
		if (anchor > 0 && nums[anchor] === nums[anchor - 1]) continue;
		let left = anchor + 1;
		let right = nums.length - 1;

		while (left < right) {
			const sum = nums[anchor] + nums[left] + nums[right];
			if (sum === 0) {
				out.push([nums[anchor], nums[left], nums[right]]);
				while (left < right && nums[left] === nums[left + 1]) left++;
				while (left < right && nums[right] === nums[right - 1]) right--;
				left++;
				right--;
			} else if (sum < 0) left++;
			else right--;
		}
	}

	return out;
}

Edge Cases & Pitfalls

• Always consider empty or null inputs.
• Watch out for off-by-one index errors.