Understanding the Problem
The Three Sum problem asks us to find all unique triplets in an array such that the sum of the three numbers is zero. In other words, we need to find all combinations of three numbers (a, b, c)
from the array where a + b + c = 0
.
It’s important to avoid returning duplicate triplets. For example, [-1, 0, 1]
and [0, -1, 1]
are considered the same triplet and should appear only once in the output.
We are going to solve this step-by-step, with a beginner-friendly explanation, and handle all edge cases carefully.
Step-by-Step Solution Using an Example
Let’s take the example array: [-1, 0, 1, 2, -1, -4]
Step 1: Sort the Array
We start by sorting the array. This helps in skipping duplicates and using the two-pointer method effectively.
Sorted array: [-4, -1, -1, 0, 1, 2]
Step 2: Fix One Element and Use Two Pointers
We loop through each element (let’s call the index i
) and treat it as the first element of a potential triplet.
Then, we use two pointers: left
starting from i + 1
and right
starting from the end of the array.
We calculate the sum of the elements at positions i
, left
, and right
and act based on the result:
- If the sum is zero: we’ve found a valid triplet. Add it to the result.
- If the sum is less than zero: we need a bigger number, so we move the
left
pointer forward.
- If the sum is more than zero: we need a smaller number, so we move the
right
pointer backward.
Step 3: Skip Duplicates
To avoid duplicate triplets:
- Skip repeated values at the
i
position.
- After finding a valid triplet, skip repeated values at
left
and right
positions.
Example Walkthrough
Let’s go through the sorted array step by step:
- i = 0: value = -4, left = 1 (-1), right = 5 (2) → sum = -3 → move left
- left = 2 (-1), right = 5 (2) → sum = -3 → move left
- left = 3 (0), right = 5 (2) → sum = -2 → move left
- left = 4 (1), right = 5 (2) → sum = -1 → move left
- i = 1: value = -1, left = 2 (-1), right = 5 (2) → sum = 0 → valid triplet [-1, -1, 2]
- Skip duplicate -1 at left, move left → left = 3 (0), right = 4 (1) → sum = 0 → valid triplet [-1, 0, 1]
- i = 2: value = -1 (duplicate), skip
- i = 3: value = 0, left = 4 (1), right = 5 (2) → sum = 3 → move right
Final result: [[-1, -1, 2], [-1, 0, 1]]
Handling Edge Cases
- Less than 3 elements: No triplets possible, return an empty list.
- All zeros: If the array is like
[0, 0, 0, 0]
, return [[0, 0, 0]]
only once.
- Empty array: Return an empty list.
- Duplicates: Skip over duplicate values during iteration to prevent redundant triplets.
Why This Approach Works
This method uses sorting + two pointers and avoids brute-force triplet checking. The time complexity is O(n²) compared to O(n³) in brute-force, making it efficient for larger inputs.
Comments
Loading comments...