TIC
The Interns Company

Three Sum

MediumAcceptance: 31.6%
ArrayTwo PointersSorting

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.

Constraints:

  • 3 <= nums.length <= 3000
  • -10^5 <= nums[i] <= 10^5

Input Format:

  • An array of integers nums

Output Format:

  • Return all triplets [nums[i], nums[j], nums[k]] that sum to zero

Examples:

Example 1:

Input:

nums = [-1,0,1,2,-1,-4]

Output:

[[-1,-1,2],[-1,0,1]]

Explanation:

The triplets that sum to zero are: [[-1,-1,2],[-1,0,1]]

Example 2:

Input:

nums = [0,1,1]

Output:

[]

Explanation:

No triplets sum to zero.

Example 3:

Input:

nums = [0,0,0]

Output:

[[0,0,0]]

Explanation:

The only triplet that sums to zero is [0,0,0].

Solutions

Two Pointers Approach

Time: O(n²)
Space: O(n) or O(log n) depending on the sorting algorithm

Sort the array first. Then, for each element, use two pointers to find pairs that sum with it to zero.

Brute Force Approach

Time: O(n³)
Space: O(n) for the result (excluding the output)

Use three nested loops to check all possible triplets.

Algorithm Walkthrough

Example input: nums = [-1,0,1,2,-1,-4]

Step-by-step execution:

  1. Sort the array: [-4, -1, -1, 0, 1, 2]
  2. i=0: nums[0]=-4, looking for pairs that sum to 4
  3. No such pairs found
  4. i=1: nums[1]=-1, looking for pairs that sum to 1
  5. left=2, right=5: nums[2]=-1, nums[5]=2, sum=0 → Add [-1,-1,2] to result
  6. i=2: nums[2]=-1 (duplicate, skip)
  7. i=3: nums[3]=0, looking for pairs that sum to 0
  8. left=4, right=5: nums[4]=1, nums[5]=2, sum=3 (too large)
  9. left=4, right=4: Invalid range, end loop
  10. i=4: nums[4]=1, looking for pairs that sum to -1
  11. No such pairs found
  12. i=5: nums[5]=2 (end of array)
  13. Return [[-1,-1,2]]

Hints

Hint 1
Sort the array first to make it easier to avoid duplicates.
Hint 2
Use two pointers to find the triplets.
Hint 3
Be careful to avoid duplicates by skipping repeated values.

Video Tutorial

3Sum - Two Pointers Approach

YouTube•Learn the Three Sum solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the sorted array and how the two pointers move to find triplets that sum to zero.

Key visualization elements:

  • current element
  • left pointer
  • right pointer
  • found triplet

Similar Questions

Two Sum

Easy

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice.

Asked By

AmazonFacebookGoogleMicrosoftAppleBloombergAdobe

Implementation Notes

This is a classic array problem that demonstrates the power of the two pointers technique. The key insight is sorting the array first to help avoid duplicates and make the solution more efficient.