Introduction

The 3 Sum problem asks us to find all unique triplets in an array whose sum is equal to 0.

A direct brute-force approach checks every possible combination of three elements.

An optimized approach uses sorting and two pointers to reduce the time complexity significantly.

Problem Statement

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

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

The solution must not contain duplicate triplets.

Example

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

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

Explanation:
-1 + (-1) + 2 = 0
-1 + 0 + 1 = 0

These are the unique triplets whose sum is 0.

Constraints

  • 3 ≤ nums.length ≤ 3000
  • -10⁵ ≤ nums[i] ≤ 10⁵
  • The result must contain only unique triplets.

Approach 1: Brute Force

Explanation

The brute-force approach considers every possible combination of three elements.

We use three loops:

  • The first loop selects the first element.
  • The second loop selects the second element.
  • The third loop selects the third element.

Whenever their sum is 0, we store the triplet.

To avoid duplicate triplets, we can sort each triplet and use a Set to store unique results.

Steps

  1. Select the first element.
  2. Select the second element.
  3. Select the third element.
  4. Calculate their sum.
  5. If the sum is 0, store the triplet.
  6. Sort the triplet before storing it.
  7. Use a Set to avoid duplicates.
  8. Return all unique triplets.

Dry Run

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

Consider:
-1, 0, 1

Sum:
-1 + 0 + 1 = 0

Triplet:
[-1, 0, 1]

Consider:
-1, -1, 2

Sum:
-1 + (-1) + 2 = 0

Triplet:
[-1, -1, 2]

Other combinations do not produce 0.

Final Result:
[[-1, -1, 2], [-1, 0, 1]]

Brute Force Code

Complexity Analysis

Time Complexity: O(n³)

Space Complexity: O(n) for storing the result and unique triplets.

Approach 2: Optimized Solution Using Sorting and Two Pointers

Explanation

The optimized approach first sorts the array.

After sorting, we fix one element and use two pointers to find the other two elements.

For every fixed element:

  • left starts immediately after it.
  • right starts at the end of the array.

If the sum is:

  • Less than 0: Move left forward.
  • Greater than 0: Move right backward.
  • Equal to 0: Store the triplet and move both pointers.

We also skip duplicate values to ensure that the result contains only unique triplets.

Steps

  1. Sort the array.
  2. Fix the first element using i.
  3. Set left = i + 1.
  4. Set right = n - 1.
  5. Calculate the sum of the three elements.
  6. If the sum is less than 0, move left forward.
  7. If the sum is greater than 0, move right backward.
  8. If the sum is 0, store the triplet.
  9. Skip duplicate values.
  10. Continue until all possible triplets are checked.

Dry Run

nums = [-1, 0, 1, 2, -1, -4]
After Sorting:
[-4, -1, -1, 0, 1, 2]

Fix i = 0:
Value = -4
left = 1
right = 5

Sum:
-4 + (-1) + 2 = -3

Sum < 0
Move left
Continue...
No valid triplet for -4.

Fix i = 1:
Value = -1
left = 2
right = 5

Sum:
-1 + (-1) + 2 = 0

Found:
[-1, -1, 2]

Move both pointers.

Next:
-1 + 0 + 1 = 0

Found:
[-1, 0, 1]

Final Result:
[[-1, -1, 2], [-1, 0, 1]]

Optimized Code

Complexity Analysis

Time Complexity: O(n²)

Sorting takes O(n log n), and the two-pointer traversal takes O(n²).

Therefore, the overall complexity is O(n²).

Space Complexity: O(1) auxiliary space, excluding the space required for the output.

Edge Cases

  • The array contains fewer than 3 elements.
  • All elements are 0.
  • No triplet has a sum of 0.
  • Multiple duplicate values exist.
  • All numbers are positive.
  • All numbers are negative.

Why This Problem is Important

The 3 Sum problem is a classic array problem that combines:

  • Sorting
  • Two Pointers
  • Duplicate handling
  • Efficient searching

It is also a common interview problem and builds the foundation for more advanced K Sum problems.

Real-World Applications

Similar techniques can be used for:

  • Finding combinations that satisfy a target.
  • Financial combination analysis.
  • Matching numerical constraints.
  • Detecting groups of values with a required total.
  • Solving higher-order Sum problems.

Common Mistakes

  • Forgetting to sort the array.
  • Not skipping duplicate values.
  • Moving the wrong pointer.
  • Forgetting to move both pointers after finding a valid triplet.
  • Using three nested loops when an O(n²) solution is expected.
  • Returning duplicate triplets.

Interview Tips

  • Start by explaining the O(n³) brute-force solution.
  • Then optimize using sorting + two pointers.
  • Clearly explain why sorting allows the pointers to move intelligently.
  • Explain how duplicate triplets are avoided.
  • Mention that the optimized complexity is O(n²).

Related Questions

  • Two Sum
  • 4 Sum
  • Container With Most Water
  • Remove Duplicates from Sorted Array
  • 3 Sum Closest

Final Takeaway

The brute-force solution checks every combination of three elements and takes O(n³) time.

The optimized solution sorts the array and uses two pointers, reducing the time complexity to O(n²).

Key Idea: Sort the array, fix one element, and use two pointers to efficiently find the remaining two elements whose sum completes the target 0.