3 Sum problem(2 pointer approach)
Here,I discussed classic problem of both 3 Sum and 4 Sum problem.
3 Sum Problem
Problem Statement
Find all unique triplets in an array whose sum equals 0.
ex-[-1, 0, 1, 2, -1, -4] o/p-[-1, -1, 2],
[-1, 0, 1]
Approach Using Two Pointers
Step 1 — Sort the Array
Sorting helps:
Use two pointers efficiently
Handle duplicates easily
Step 2 — Fix One Element
Choose one element at a time.
For example:
Fix -1
Now we need two more numbers whose sum becomes 1
Step 3 — Use Two Pointers
Place:
One pointer after the fixed element
One pointer at the end
Now:
If the sum is too small → move left pointer forward
If the sum is too large → move right pointer backward
If the required sum is found → store the triplet
This reduces the complexity from O(n³) to O(n²).
Important Observation
Since the array is sorted:
Moving left pointer increases the sum
Moving right pointer decreases the sum
This is the main reason why the two pointer technique works efficiently.
Handling Duplicates
Duplicate triplets should not appear in the final answer.
So while traversing:
Skip repeated fixed elements
Skip repeated pointer values after finding a valid triplet
This ensures only unique triplets are stored.
Time Complexity of 3 Sum
| Approach | Complexity |
| -------------------- | ---------- |
| Brute Force | O(n³) |
| Two Pointer Approach | O(n²) |
4 Sum
Problem Statement
Find all unique quadruplets whose sum equals a given target.
Example:nums = [1,0,-1,0,-2,2]
target = 0
o/p-[-2,-1,1,2]
[-2,0,0,2]
[-1,0,0,1]
Approach Using Two Pointers
The logic is very similar to the 3 Sum problem.
Step 1 — Sort the Array
Sorting again helps in:
Efficient traversal
Duplicate handling
Applying two pointers
Step 2 — Fix Two Elements
In 4 Sum:
First fix one element
Then fix a second element
Now we only need to find two remaining numbers.
This becomes similar to the 2 Sum problem.
Step 3 — Apply Two Pointers
Use:
Left pointer
Right pointer
Now:
Increase left pointer if sum is smaller
Decrease right pointer if sum is larger
Store answer if target is achieved
Why 4 Sum Becomes Efficient
Brute force checks every quadruplet:O(n⁴)
Using sorting + two pointers:O(n³)
Click it to see the codes of both
Key Takeaways
The 3 Sum and 4 Sum problems are powerful examples of:
How sorting simplifies problems
How two pointers reduce complexity
How observation can optimize brute force solutions
The two pointer technique is widely used in:
Pair sum problems
Sliding window problems
Array optimization questions
Interview-level DSA questions
Mastering this technique makes many advanced problems easier.
Conclusion
The biggest lesson from 3 Sum and 4 Sum is that:
A sorted array combined with smart pointer movement can eliminate unnecessary computations efficiently.
Instead of checking every possible combination:
We intelligently move pointers
Reduce time complexity
Avoid duplicates naturally
These problems are a must-learn for anyone preparing for coding interviews or competitive programming.
Top comments (0)