3Sum LeetCode 15 Solution: Two Pointers & Triplets for FAANG

Pattern Recognition — 3Sum (LeetCode 15)

Many candidates struggle to identify 3Sum as an extension of Two Sum. Recognizing this pattern early in an interview saves time and demonstrates problem-solving skills.

Key Pattern Clues

• Problem asks for **all unique triplets** summing to a target (often 0).
• Input array may contain **negative, positive, and zero numbers**.
• Output must **avoid duplicates**, hinting at sorting + two-pointer strategy.
• Mentions of “**triplets**” instead of pairs often signal 3Sum.

Relation to Two Sum & Two Sum II

Problem	Core Pattern	Optimal Approach	Beginner Tip
Two Sum	Find two numbers = target	Hash map O(n)	Check complement before inserting
Two Sum II	Sorted array → two pointers	O(n) with left/right pointers	Move pointers based on sum comparison
3Sum	Fix one element, find pair summing to complement	Sort + two pointers → O(n²)	Skip duplicates, dry-run on small arrays

ASCII Flow — Visualizing Two Pointers for 3Sum

Example: nums = [-4,-1,-1,0,1,2], target sum = 0

Step 1: Sort the array
[-4, -1, -1, 0, 1, 2]

Step 2: Fix first element (-4)
Left pointer → -1, Right pointer → 2
Sum = -4 + (-1) + 2 = -3 → <0, move left++
Left → -1, Right → 2
Sum = -4 + (-1) + 2 = -3 → <0, move left++
...

Step 3: Fix first element (-1)
Left → -1, Right → 2
Sum = -1 + (-1) + 2 = 0 ✅ found triplet [-1,-1,2]
Skip duplicates: move left++ and right--
Next: Left → 0, Right → 1
Sum = -1 + 0 + 1 = 0 ✅ found triplet [-1,0,1]
...

Beginner Tips to Spot 3Sum

• If problem says “**all unique triplets**,” think sorting + two pointers.
• Identify if target is fixed (e.g., 0), then reduce problem to Two Sum for remaining array.
• Look for language like “**no duplicates**,” “**return all combinations**.”
• Draw small examples to simulate pointer movement and detect patterns visually.

Interview Insights

• Interviewer expects you to recognize 3Sum as **Two Sum + fixed element** pattern.
• Explain why sorting helps: duplicate removal & pointer efficiency.
• Dry-run examples aloud, mention time complexity (O(n²)) and space usage.
• Optional: discuss follow-ups (4Sum, kSum) to show problem generalization ability.

Pattern Progression Table

Pattern	Problem Type	Pointer/Map Usage	Complexity
Two Sum	Pair sum	Hash map	O(n)
Two Sum II	Pair sum (sorted)	Two pointers	O(n)
3Sum	Triplets sum	Fix one + two pointers	O(n²)
4Sum / kSum	k-sum combinations	Recursion + two pointers	O(n^(k-1))

Interview-Focused — Short Answer to Deliver (Two Sum II)

"Start by stating brute-force checks all pairs (O(n²)) for correctness. Then mention the optimized two-pointer approach: initialize left and right, compute sum = nums[left] + nums[right]. Move pointers toward each other based on sum comparison. Return the first valid pair. This achieves O(n) time and O(1) space. Mention handling of duplicates, minimal array size, negatives, and confirm sorted input."

One-minute checklist to say

• Restate problem and confirm constraints (sorted, indices, duplicates).
• Explain why brute-force is slow (O(n²)).
• Explain two-pointer approach, pointer movements, and early return.
• Do a dry-run on a sample array (e.g., [2,7,11,15], target=9).
• Mention edge cases and potential follow-ups: duplicates, negatives, multiple pairs.
• Highlight O(n) time and O(1) space efficiency.

Interview Script & What to Say (Two Sum II — Sorted Array)

Step-by-step script (word-for-word suggestions)

1. "I'll restate the problem: given a sorted array nums and target, return the 1-indexed positions of two numbers that sum to target. Are duplicates possible and do I return the first valid pair?"
2. "Since the array is sorted, a brute-force approach of checking all pairs is O(n²). It's correct but not optimal for large inputs."
3. "A better approach is two-pointer. Initialize left=0, right=nums.length-1. Compute sum = nums[left] + nums[right]. If sum == target, return [left+1, right+1]. If sum < target, move left++. If sum > target, move right--. This runs in O(n) time and O(1) space."
4. Dry-run a small example out loud: nums=[2,7,11,15], target=9.
5. "Edge cases: minimal array size (2), duplicates, negatives, and multiple valid pairs. Always confirm array is sorted before assuming two-pointer."

What the interviewer hears

• Clear problem restatement and constraints check.
• Recognition of input properties (sorted array) and optimal approach.
• Ability to communicate pointer movement strategy, dry run, and early exit.
• Consideration of edge cases and follow-up questions.

Solution Approach — 3Sum (LeetCode 15)

The optimal approach builds on the Two Sum II pattern: sort the array, fix one element, and use two pointers to find pairs summing to the complement. This ensures O(n²) time and avoids duplicates.

Step-by-step Algorithm (Beginner-Friendly)

1. Sort the array in ascending order.
2. Iterate with index i from 0 to nums.length - 3. Fix nums[i] as the first element.
3. Skip duplicates for nums[i] to avoid repeated triplets.
4. Set two pointers: left = i+1, right = nums.length-1.
5. While left < right:
   • Calculate sum = nums[i] + nums[left] + nums[right].
   • If sum < target → move left++.
   • If sum > target → move right--.
   • If sum == target → add triplet, skip duplicates, move both pointers.

JavaScript Dry-Run Example

const nums = [-1, 0, 1, 2, -1, -4];
nums.sort((a,b) => a-b); // [-4,-1,-1,0,1,2]
const target = 0;
const result = [];

for (let i = 0; i < nums.length-2; i++) {
  if (i > 0 && nums[i] === nums[i-1]) continue; // skip duplicates

  let left = i+1, right = nums.length-1;
  while (left < right) {
    const sum = nums[i] + nums[left] + nums[right];
    if (sum < target) left++;
    else if (sum > target) right--;
    else {
      result.push([nums[i], nums[left], nums[right]]);
      while (nums[left] === nums[left+1]) left++;  // skip duplicates
      while (nums[right] === nums[right-1]) right--;  // skip duplicates
      left++; right--;
    }
  }
}

console.log(result); // [[-1,-1,2],[-1,0,1]]

ASCII Visualization — Pointer Movement

Sorted array: [-4, -1, -1, 0, 1, 2]

i = 0 → nums[i] = -4
Left = 1 (-1), Right = 5 (2)
Sum = -4 + (-1) + 2 = -3 → <0 → left++

Left = 2 (-1), Right = 5 (2)
Sum = -4 + (-1) + 2 = -3 → left++

...

i = 1 → nums[i] = -1
Left = 2 (-1), Right = 5 (2)
Sum = -1 + (-1) + 2 = 0 ✅ add [-1,-1,2], move pointers skipping duplicates
Next: Left = 3 (0), Right = 4 (1)
Sum = -1 + 0 + 1 = 0 ✅ add [-1,0,1]
...

Beginner-Friendly Notes

• Sorting ensures duplicate handling and pointer efficiency.
• Always skip duplicates for i, left, and right to avoid repeated triplets.
• Time complexity: O(n²), space complexity: O(1) extra (ignoring output).
• Dry-run small arrays to understand pointer movement before writing code.
• Relates directly to Two Sum II: fix one element, then reduce to Two Sum problem.

Interview Tips

• Explain the reduction from 3Sum → Two Sum II for the remaining array.
• Mention why sorting is essential.
• Highlight duplicate handling to avoid repeated triplets.
• Walk through a dry-run example to show correctness and understanding.

Deep Dive — 3Sum (LeetCode 15)

Correctness Invariant (Pointer Logic)

At each iteration with fixed nums[i], the two pointers left and right scan the remaining sorted array for pairs summing to -nums[i]. Invariant: All indices <i have already been processed, and duplicate triplets are skipped.

Why sorting and skipping duplicates matter

• Sorting ensures duplicates appear consecutively, enabling us to skip them efficiently.
• Skipping duplicates for i, left, and right prevents repeated triplets.
• Pointer movement guarantees that we find all valid pairs for the fixed element without revisiting the same elements.

Pointer Movement Reasoning

Let nums[i] be fixed. Left and right pointers traverse the remaining array:

• If sum < 0 → move left++ to increase sum.
• If sum > 0 → move right-- to decrease sum.
• If sum == 0 → store triplet, skip duplicates, move both pointers.

Variants & Trade-Offs (What Interviewers May Ask)

• Return count instead of triplets: Can be done similarly with minor modification, reducing output memory.
• Return unique triplets without sorting: Requires hash set to track duplicates, more memory-heavy.
• k-Sum generalization: Recursive reduction: fix one element, reduce to (k-1)-Sum problem.
• Memory tight: Sort in-place, O(1) extra space.

Micro-Optimizations

• Early termination: if nums[i] > 0 → break loop (remaining numbers positive → sum cannot be 0).
• Use while loops to skip duplicates efficiently instead of re-checking inside for-loops.
• Reduce unnecessary array accesses by caching nums[i], nums[left], nums[right].

Proof Sketch (Short)

Every triplet [nums[i], nums[left], nums[right]] is found because:

1. For fixed nums[i], all remaining pairs (left, right) are checked in sorted order.
2. Duplicate triplets are skipped due to sorting + duplicate checks.
3. If a valid triplet exists with indices a < b < c, when the loop reaches nums[a] as i, pointers left and right will eventually find b and c.

Hence, all unique triplets summing to zero are captured correctly.

Comparison to Two Sum I & II

Problem	Technique	Time Complexity	Key Difference
Two Sum I	Hash Map (one-pass)	O(n)	Unsorted, find pair of indices
Two Sum II (Sorted)	Two Pointers	O(n)	Sorted array, find pair values
Three Sum (3Sum)	Fix one + Two Pointers	O(n²)	Find triplets, skip duplicates, reduce to Two Sum II

Common Pitfalls — 3Sum (LeetCode 15)

1. Not skipping duplicates properly

Forgetting to skip duplicate elements for i, left, or right leads to repeated triplets. Example: nums = [-1, -1, 0, 1, 1], not skipping duplicates produces [-1, 0, 1] twice.

2. Pointer mismanagement

• Moving left and right incorrectly after finding a triplet → can miss valid triplets or cause infinite loops.
• Not adjusting pointers based on sum comparison (sum < 0 → left++, sum > 0 → right--) → incorrect results.

3. Index errors

• Using i, left, right incorrectly outside array bounds.
• Mixing up indices vs. values (especially if returning indices instead of values in some variants).

4. Assuming array is unsorted

Unlike Two Sum I, 3Sum requires sorting for the two-pointer approach. Attempting pointer logic on an unsorted array yields wrong answers.

5. Comparison to Two Sum I & II

Problem	Common Mistakes
Two Sum I (Unsorted)	Using two pointers without sorting, forgetting hash map edge cases
Two Sum II (Sorted)	Pointer mismanagement, not skipping duplicates if asked for unique pairs
Three Sum (3Sum)	Not skipping duplicates, pointer mismanagement, index errors, assuming unsorted array

6. Edge scenarios beginners often miss

• All zeros → triplet [0,0,0]
• All negatives or positives → early termination possible
• Minimal length arrays < 3 → no solution

Interview Tip

Explain your duplicate skipping strategy, pointer movement logic, and reasoning about sorted array. Demonstrating awareness of these pitfalls impresses interviewers.

Edge Cases — 3Sum (LeetCode 15)

1. Arrays with less than 3 elements

If nums.length < 3, there is no possible triplet. Always check this first to avoid unnecessary processing.

  Example: nums = [1, 2]
  Output: []
  

2. All zeros

Special case where multiple zeros exist. Only one triplet [0,0,0] should be returned if duplicates are skipped.

  nums = [0,0,0,0]
  Sorted: [0,0,0,0]

  i=0, left=1, right=3
  sum = 0 + 0 + 0 = 0 → valid triplet [0,0,0]
  Skip duplicates:
    left++ → 2,3
    right-- → 2,1 → loop ends
  Output: [[0,0,0]]
  

3. All positives or all negatives

Early termination possible:

  nums = [-5, -3, -1]
  Since all numbers < 0, sum > 0 never occurs → no triplets possible

  nums = [1, 2, 3]
  Since all numbers > 0, sum < 0 never occurs → no triplets possible
  

4. Duplicates in the middle

Skipping duplicates for i, left, right is essential to avoid repeated triplets.

  nums = [-1, -1, 0, 1, 1]
  i=0 → nums[i]=-1
    left=1 → skip -1 duplicate → left=2
    right=4 → sum=-1+0+1=0 → valid
  Output: [[-1,0,1]]
  

5. Suggested interview demonstration

Use small examples to show pointer movement, duplicate skipping, and sum evaluation. Verbally explain:

  nums = [-2,0,0,2,2]
  Sorted: [-2,0,0,2,2]

  i=0 → nums[i]=-2
    left=1 → 0
    right=4 → 2
    sum=-2+0+2=0 → triplet [-2,0,2]
    Skip duplicates:
      left=2 → skip 0 duplicate → left=3
      right=3 → loop ends

  Output: [[-2,0,2]]
  

6. Minimal edge arrays

• nums = [] → []
• nums = [0,0] → []
• nums = [0,0,0] → [[0,0,0]]

Interviewers expect awareness of these edge cases and clear demonstration of handling duplicates and pointer logic.

Time & Space Complexity — 3Sum (LeetCode 15)

1. Time Complexity

The standard approach uses sorting + two pointers:

1. Sort the array: O(n log n)
2. Iterate through each element i (0..n-3) and for each, run two pointers left and right: O(n²)

Therefore, total time complexity is:

    O(n log n) + O(n²) → O(n²)
  

Dry-run reasoning:

    nums = [-1,0,1,2,-1,-4] → sort → [-4,-1,-1,0,1,2]

    i=0 → nums[i]=-4, left=1, right=5 → move pointers
    i=1 → nums[i]=-1, left=2, right=5 → move pointers
    i=2 → nums[i]=-1 (skip duplicate)
    i=3 → nums[i]=0, left=4, right=5 → move pointers

    Each i may process up to n elements with left/right → O(n²)
  

2. Space Complexity

Auxiliary space:

• Sorting in-place → O(log n) recursion stack if using quicksort (or O(n) for mergesort)
• Two pointers → O(1) extra space
• Output array → depends on number of unique triplets, worst-case O(n²) (not counted in algorithmic space)

3. Beginner-Friendly Illustration

    nums = [-1,0,1,2,-1,-4]
    Sorted: [-4,-1,-1,0,1,2]

    i=0 → -4
      left=1 → -1
      right=5 → 2
      sum=-4+-1+2=-3 < 0 → left++
      left=2 → -1
      sum=-4+-1+2=-3 → left++
      ...
    
    Each i loops through left/right pointers → O(n) per i
    Total iterations ~ n*(n-1)/2 → O(n²)
  

4. Key Takeaways for Interviews

• Always mention sorting step for time complexity clarity.
• Two pointers avoid O(n³) brute-force.
• Space is minimal; only output array grows depending on number of triplets.
• Explain pointer movements in dry-run for clarity to interviewer.

5. Comparison with Two Sum / Two Sum II

Problem	Approach	Time Complexity	Space Complexity
Two Sum (unsorted)	Hash Map	O(n)	O(n)
Two Sum II (sorted)	Two Pointers	O(n)	O(1)
Three Sum	Sort + Two Pointers	O(n²)	O(1) auxiliary

Related Problems — 3Sum (LeetCode 15)

1. Variant Comparisons

3Sum is an extension of Two Sum problems. Understanding the variants helps in interview prep:

Problem	Input	Goal	Approach	Complexity
Two Sum (LC1)	Unsorted array	Find indices of 2 numbers summing to target	Hash Map → O(n)	Time: O(n), Space: O(n)
Two Sum II (LC167)	Sorted array	Find indices of 2 numbers summing to target	Two Pointers → O(n)	Time: O(n), Space: O(1)
Three Sum (LC15)	Unsorted array	Find all unique triplets summing to 0	Sort + Two Pointers → O(n²)	Time: O(n²), Space: O(1) auxiliary
3Sum Closest (LC16)	Unsorted array, target value	Find triplet sum closest to target	Sort + Two Pointers → O(n²)	Time: O(n²), Space: O(1)
4Sum (LC18)	Unsorted array	Find all quadruplets summing to target	Sort + k-pointers / Hash Map → O(n³)	Time: O(n³), Space: O(1) auxiliary
Subarray Sum Equals K (LC560)	Array, target sum	Count subarrays summing to k	Hash Map Prefix Sum → O(n)	Time: O(n), Space: O(n)

2. Progression Path

To build a strong DSA foundation, follow this problem progression:

1. Two Sum (LC1) — Understand brute-force and hash map optimization.
2. Two Sum II (LC167) — Learn two-pointer approach on sorted arrays.
3. Three Sum (LC15) — Extend two-pointer to triplets, handle duplicates carefully.
4. 3Sum Closest (LC16) — Focus on optimization for nearest target sums.
5. 4Sum (LC18) — Generalize k-sum technique.
6. Subarray Sum Variants — Hash map and prefix sum strategies.

3. Interview Practice Strategy

• Start with **Two Sum** variants — hash map & two pointers — ensure you can explain time/space complexity.
• Practice **3Sum** with small examples first, then medium-sized arrays to dry-run two-pointer approach.
• Learn to **handle duplicates** effectively using skip logic.
• Compare **3Sum vs 2Sum II** in your explanation to show pattern recognition skills.
• Attempt **follow-ups**: 3Sum Closest, 4Sum — discuss trade-offs in time and space.
• Use **ASCII diagrams** to demonstrate pointer movement in interviews — it impresses interviewers.
• Finally, practice **edge cases** and **micro-optimizations** (skip duplicates early, early exit conditions, etc.)

4. Key Takeaways

• 3Sum is the natural extension of Two Sum → recognize sorted vs unsorted patterns.
• Two-pointer + sorting is the optimal approach for triplets in unsorted arrays.
• Interviewers expect dry-run reasoning, duplicate handling, and clear complexity explanation.
• Progressively moving from 2Sum → 3Sum → 4Sum helps build confidence for k-sum problems.

FAQs — 3Sum (LeetCode 15)

1. What is the 3Sum Problem?

Given an array of integers, find all unique triplets [a, b, c] such that a + b + c = 0. Example: nums = [-1,0,1,2,-1,-4] → [[-1,-1,2],[-1,0,1]]

2. What is the optimal approach?

Sort the array first, then use a **two-pointer technique** for each element as the first of the triplet. Skip duplicates to ensure unique triplets. This gives O(n²) time and O(1) extra space.

3. Why sorting is necessary?

• Enables **two-pointer movement**: left/right pointers approach each other based on sum.
• Allows **efficient duplicate skipping** to avoid repeated triplets.
• Without sorting, you’d need a hash set of arrays → higher complexity and error-prone.

4. Key micro-optimizations to mention in interviews

• Skip elements if they are the same as the previous one to avoid duplicate triplets.
• If current element > 0, break early since sum cannot be zero with remaining positive numbers.
• Return results immediately if sum matches and adjust pointers carefully.
• Use ASCII diagrams in dry-run to explain pointer movements step-by-step.

5. Common interview mistakes

• Failing to skip duplicates leading to repeated triplets.
• Not sorting before two-pointer step.
• Incorrect pointer updates causing infinite loops.
• Returning indices instead of actual triplets (or vice versa based on question).

6. How to explain this problem in an interview?

1. Restate the problem clearly: "Find all unique triplets summing to zero."
2. Show brute-force approach (triple nested loop) for correctness.
3. Optimize with sorting + two-pointer approach, explaining pointer movement and duplicate skipping.
4. Discuss time/space complexity (O(n²) / O(1) extra space).
5. Dry-run a small example out loud using ASCII pointer diagrams.
6. Mention edge cases: empty array, fewer than 3 elements, duplicates, all positive or negative numbers.

7. How does 3Sum relate to Two Sum I & II?

3Sum is a natural extension: Two Sum handles pairs, 3Sum handles triplets. Two-pointer approach in **sorted arrays** is reused for the inner loop of 3Sum, while brute-force or hash map logic applies for unsorted variants.

8. Follow-up problems for practice

• 3Sum Closest (LC16) — find closest sum to a target.
• 4Sum (LC18) — extend to quadruplets.
• k-Sum generalized problems.
• Subarray sum problems (LC560, LC325) to practice hash map + prefix sum techniques.