3Sum is a classic Two Pointer problem. Sorting the array is the key step because it allows duplicate removal and enables the two-pointer technique. Whenever a problem involves finding pairs or triplets in a sorted array, think about using Two Pointers instead of nested loops. This pattern appears in many interview problems like 3Sum Closest, 4Sum, Container With Most Water, and Trapping Rain Water.
Problem stats
Before
Use three nested loops to check every possible triplet.
1. Pick the first number.
2. Pick the second number.
3. Pick the third number.
4. If their sum equals zero, store the triplet.
5. Use a Set to avoid duplicate triplets.
This approach checks every combination and is very slow for large inputs.
After
First sort the array.
Fix one element at a time.
Use two pointers:
- left = current index + 1
- right = last index
Calculate the sum.
If sum is zero:
- Store the triplet.
- Skip duplicate values.
- Move both pointers.
If sum is smaller than zero:
- Move the left pointer.
If sum is greater than zero:
- Move the right pointer.
Repeat until all possible triplets are found.
Sorting helps eliminate duplicates efficiently and allows the two-pointer technique to run in O(n²).
The optimized implementation, ready for interview preparation and quick revision.
Solution.java
1import java.util.*;2 3public class Solution {4 5 public List<List<Integer>> threeSum(int[] nums) {6 7 List<List<Integer>> result = new ArrayList<>();8 9 Arrays.sort(nums);10 11 for (int i = 0; i < nums.length - 2; i++) {12 13 if (i > 0 && nums[i] == nums[i - 1]) {14 continue;15 }16 17 int left = i + 1;18 int right = nums.length - 1;19 20 while (left < right) {21 22 int sum = nums[i] + nums[left] + nums[right];23 24 if (sum == 0) {25 26 result.add(Arrays.asList(27 nums[i],28 nums[left],29 nums[right]30 ));31 32 while (left < right && nums[left] == nums[left + 1]) {33 left++;34 }35 36 while (left < right && nums[right] == nums[right - 1]) {37 right--;38 }39 40 left++;41 right--;42 43 } else if (sum < 0) {44 45 left++;46 47 } else {48 49 right--;50 }51 }52 }53 54 return result;55 }56 57 public static void main(String[] args) {58 59 Solution solution = new Solution();60 61 int[] nums = {-1, 0, 1, 2, -1, -4};62 63 System.out.println(solution.threeSum(nums));64 }65}Analyze the efficiency of the algorithm by understanding its time and space complexity across different execution scenarios.
Time complexity
Space complexity
By execution case
Best case
O(n²)
Average case
O(n²)
Worst case
O(n²)
This solution achieves a O(n²) time complexity while using O(1) extra memory. It is considered the optimal approach for this problem and is suitable for coding interviews as well as competitive programming.
Every coding problem teaches a pattern. Focus on the concepts, avoid common mistakes, and remember the interview-worthy takeaways instead of memorizing code.
The biggest takeaway from this problem.
3Sum is a classic Two Pointer problem. Sorting the array is the key step because it allows duplicate removal and enables the two-pointer technique. Whenever a problem involves finding pairs or triplets in a sorted array, think about using Two Pointers instead of nested loops. This pattern appears in many interview problems like 3Sum Closest, 4Sum, Container With Most Water, and Trapping Rain Water.
Explain why the optimized solution works before writing the final code. Interviewers care about your thinking process as much as your implementation.
Avoid jumping directly to coding. Always analyze edge cases, constraints, and the optimal approach before implementation.
Focus on understanding the algorithm's pattern instead of memorizing the code. Once the logic becomes clear, implementing the solution in any programming language becomes much easier.
Every DSA problem introduces a reusable pattern. Instead of remembering the exact solution, remember the thought process that led to it. Over time, these patterns will help you solve new problems much faster and perform better in coding interviews.
Practice consistently and move through the roadmap one problem at a time.
Practice similar problems to strengthen your understanding of the underlying algorithm and improve pattern recognition.
More practice problems will be added soon.