DATA STRUCTURES • ALGORITHMS

Three Sum Problem

Find all unique triplets in an array that sum up to exactly zero.

Time

O(N²)

Space

O(log N) or O(N) (Sorting space)

Key Principle 1

Sort the array to use two pointers

Key Principle 2

Fixed pointer 'i' + L/R pointers

Key Principle 3

Handle duplicates to avoid same triplets

Key Principle 4

Skip same elements to optimize

3SUM_LAB
Current Step
Goal: Find all unique triplets that sum to 0. First, sort the array.
Playback
Triplets Found
None yet
Sum Calculation ⠿
Fixed (i)-
Left (L)-
Right (R)-
SUM-
Two Pointer Logic ⠿
1sort(nums);
2for (int i = 0; i < n - 2; i++) {
3    int L = i + 1, R = n - 1;
4    while (L < R) {
5        int sum = nums[i] + nums[L] + nums[R];
6        if (sum == 0) addTriplets();
7        else if (sum < 0) L++;
8        else R--;
9    }
10}
-4
[0]
-1
[1]
-1
[2]
0
[3]
1
[4]
2
[5]

Loading Lab...