Plaintext
================================================================================
BLOG ARTICLE CONTENT (Markdown / HTML)
================================================================================
# 180-Day DSA Roadmap | Day 2: 3Sum (LeetCode #15)
* **Topic:** Arrays & Strings
* **Pattern:** Two Pointers (Fixed Pivot + Inward Scan)
* **Difficulty:** Medium
* **LeetCode Problem:** LeetCode #15 - 3Sum
* **Target Companies:** Meta, Amazon, Microsoft, Apple, Google, Adobe
---
## 1. Problem Statement
Given an integer array `nums`, return all the triplets `[nums[i], nums[j], nums[k]]` such that:
* `i != j`, `i != k`, and `j != k` (all indices are distinct)
* `nums[i] + nums[j] + nums[k] == 0`
Notice that the solution set **must not contain duplicate triplets**.
### Constraints
* 3 <= nums.length <= 3000
* -10^5 <= nums[i] <= 10^5
* Result triplets can be returned in any order.
### Example Walkthrough
```text
Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1, 0, 1] and [-1, -1, 2].
Notice that [-1, 0, 1] and [0, 1, -1] are identical triplets; only one must be included.
2. Pattern Recognition: Why Reduce to Two Pointers?
3Sum is the natural extension of Day 1’s Two Sum II:
- Equation Transformation:
$$a + b + c = 0 \implies b + c = -a$$If you fix elementa, the problem becomes finding two numbersbandcthat add up to a target of-a. - Why Sort First?
- Sorting takes $O(N \log N)$, while checking all combinations takes $O(N^3)$.
- Once sorted, identical numbers cluster together side-by-side. This makes skipping duplicate triplets straightforward in $O(1)$ memory without needing a hash set.
- Sorting unlocks the monotonic two-pointer approach, reducing each subproblem from $O(N^2)$ to $O(N)$.
3. Algorithmic Approaches
Approach 1: Brute Force (Fails)
- Generate all triplet combinations using 3 nested loops and filter duplicates using a set.
- Time Complexity: $O(N^3)$
- Space Complexity: $O(N)$
- Verdict: Time Limit Exceeded (TLE).
Approach 2: Hash Set Lookups (Suboptimal)
- Fix one number, then run standard Two Sum with an internal hash set for the remaining pair.
- Time Complexity: $O(N^2)$
- Space Complexity: $O(N)$
- Verdict: Passes, but sorting hash tuples to avoid duplicate permutations creates heavy memory and runtime overhead.
Approach 3: Sort + Two Pointers (Optimal MNC Standard)
- Sort
numsin ascending order. - Iterate through the array with pointer
ifrom0ton - 3:- Early Exit: If
nums[i] > 0, break immediately. In a sorted array, if the smallest number is positive, three numbers can never sum to zero. - Skip Duplicates for
i: Ifi > 0andnums[i] == nums[i - 1], continue to the next iteration.
- Early Exit: If
- For each fixed
i, initializeleft = i + 1andright = n - 1:- If
nums[i] + nums[left] + nums[right] == 0:- Add
[nums[i], nums[left], nums[right]]to the result. - Advance
leftpast any duplicate values:while (left < right && nums[left] == nums[left + 1]) left++; - Decrement
rightpast any duplicate values:while (left < right && nums[right] == nums[right - 1]) right--; - Take the final step:
left++,right--.
- Add
- If the sum is
< 0: Incrementleft++to increase the total. - If the sum is
> 0: Decrementright--to decrease the total.
- If
Plaintext
Visual Execution Trace:
Sorted nums = [-4, -1, -1, 0, 1, 2]
Fixed i = 1 (nums[1] = -1):
Target for (left + right) = -(-1) = 1
[-4, -1, -1, 0, 1, 2]
▲ ▲ ▲
i left right Sum = -1 + (-1) + 2 = 0 ──► FOUND [-1, -1, 2]!
Skip duplicate left/right, move inward.
[-4, -1, -1, 0, 1, 2]
▲ ▲ ▲
i left right Sum = -1 + 0 + 1 = 0 ──► FOUND [-1, 0, 1]!
4. Production-Ready Code Implementations
Java Solution
Java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
int n = nums.length;
for (int i = 0; i < n - 2; i++) {
if (nums[i] > 0) break; // Cannot sum to 0 if smallest value is > 0
if (i > 0 && nums[i] == nums[i - 1]) continue; // Skip duplicate pivot
int left = i + 1;
int right = n - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
// Skip duplicate values for left and right pointers
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
}
Python 3 Solution
Python
class Solution:
def threeSum(self, nums: list[int]) -> list[list[int]]:
nums.sort()
result = []
n = len(nums)
for i in range(n - 2):
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, n - 1
while left < right:
curr_sum = nums[i] + nums[left] + nums[right]
if curr_sum == 0:
result.append([nums[i], nums[left], nums[right]])
# Skip duplicate values
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif curr_sum < 0:
left += 1
else:
right -= 1
return result
C++ Solution
C++
#include <vector>
#include <algorithm>
class Solution {
public:
std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
std::sort(nums.begin(), nums.end());
std::vector<std::vector<int>> result;
int n = nums.size();
for (int i = 0; i < n - 2; ++i) {
if (nums[i] > 0) break;
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1;
int right = n - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.push_back({nums[i], nums[left], nums[right]});
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
};
5. Complexity Analysis
- Time Complexity: $O(N^2)$
Sorting takes $O(N \log N)$. The outer loop runs $N$ times, and each inner two-pointer search takes $O(N)$ operations. Total runtime is $O(N \log N + N^2) = O(N^2)$. - Space Complexity: $O(1)$ or $O(\log N)$
Excluding the memory required to store the output list, auxiliary space is limited to variables and the space consumed by the sorting algorithm ($O(\log N)$ in C++/Java quicksort/timsort).
6. Key Takeaways & Common Interview Traps
- The Hash Set Trap: Do not use
Set<List<Integer>>to filter duplicates. Interviewers look for pointer skipping logic (while nums[left] == nums[left+1]) to prove you understand in-place array invariants. - Why Advance Twice? The while loop only moves pointers to the last identical duplicate. You must call
left++andright--one additional time to land on a completely new value.
Master 3Sum (LeetCode 15) using Two Pointers: Avoid Duplicate Traps | Day 2 of 180
META DESCRIPTION:
Master LeetCode 15 (3Sum) using sorting and two pointers. Learn how to handle duplicate triplets in O(1) space with complete code in Java, Python, and C++.
3Sum LeetCode 15, Two Pointer 3Sum Algorithm, LeetCode 15 Java Python Cpp, Three Sum Duplicate Handling
leetcode 15, 3sum, three sum problem, two pointers technique, dsa roadmap, dsa interview questions, coding interview preparation, data structures and algorithms, leetcode solutions, two pointers pattern, leetcode medium, faang interview preparation, mnc coding questions, amazon coding interview, google coding interview, microsoft interview questions, meta coding interview, leetcode 15 java, leetcode 15 python, leetcode 15 cpp, java dsa, python dsa, cpp dsa, time complexity o n2, space complexity o 1, array interview questions, k sum problem, sorted array two sum, top dsa patterns, software engineer jobs, campus placement preparation, competitive programming, vs coding academy, 180 days dsa, dsa cheat sheet, cracking the coding interview, tech interview prep, leetcode patterns, software development engineer, sde 1 preparation, array algorithms, inplace algorithms, duplicate triplet handling, coding questions for freshers, dsa placement series, engineering placements, leetcode practice, data structures roadmap, algorithm patterns, technical interview tips, leetcode daily streak
Follow our YouTube Channels:
Trendy VS Vlogs: https://youtube.com/@trendyvsvlogs?si=Xd3L31p5zPXggomY
WhatsApp Channel: https://whatsapp.com/channel/0029Vb9H4vC545v2HaoKk735