LeetCode Pattern/Two Pointers/Advanced Two Pointers: 3Sum, 4Sum, and Multi-Pointer Techniques

Advanced Two Pointers: 3Sum, 4Sum, and Multi-Pointer Techniques

LeetCopilot Team

Dec 9, 2025

16 min read

Two Pointers3Sum4Sumk-SumAdvanced PatternsInterview Prep

Master advanced multi-pointer patterns that extend beyond basic two pointers. Learn 3Sum, 4Sum, k-Sum generalization, and how to handle duplicates at scale.

Complete Guide

The Complete Two Pointers Guide: Master All Patterns, Templates, and Techniques

The ultimate comprehensive guide to two pointers. Learn all variants, when to use each pattern, complete templates in multiple languages, and a systematic approach to solve any two pointers problem.

Read the complete guide

You've mastered Two Sum with two pointers. The pattern is clear, the code is elegant.

Then you encounter 3Sum. "Find all triplets that sum to zero."

Your first thought: "Can I just... add another pointer?"

Yes! But there's more to it. 3Sum isn't just Two Sum with an extra loop—it requires careful duplicate handling, optimization techniques, and a deeper understanding of how pointers interact.

And beyond 3Sum lies 4Sum, k-Sum, and a whole family of multi-pointer problems that appear constantly in interviews.

This comprehensive guide will teach you advanced multi-pointer techniques, from 3Sum to k-Sum generalization, with duplicate handling, optimization tricks, and patterns that scale to any number of pointers.

TL;DR

Multi-pointer pattern:

Fix k-2 elements with nested loops
Use two pointers on the remaining array
Skip duplicates at each level

Complexity:

3Sum: O(n²)
4Sum: O(n³)
k-Sum: O(n^(k-1))

Template:

python

nums.sort()
for i in range(len(nums) - k + 1):
    if i > 0 and nums[i] == nums[i-1]:
        continue  # Skip duplicates
    # Recursively solve (k-1)-Sum

The Multi-Pointer Framework

From 2-Sum to k-Sum

Pattern evolution:

2-Sum: Two pointers (O(n))
3-Sum: Fix 1 element + Two pointers (O(n²))
4-Sum: Fix 2 elements + Two pointers (O(n³))
k-Sum: Fix k-2 elements + Two pointers (O(n^(k-1)))

Key insight: Each additional element adds one loop level.

Pattern 1: 3Sum (The Foundation)

Problem

Find all unique triplets that sum to zero.

Complete Solution

python

def threeSum(nums: List[int]) -> List[List[int]]:
    """
    LeetCode #15: 3Sum
    
    Time: O(n²)
    Space: O(1) excluding output
    """
    nums.sort()
    result = []
    n = len(nums)
    
    for i in range(n - 2):
        # Skip duplicates for i
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        # Early termination
        if nums[i] > 0:
            break  # All remaining numbers are positive
        
        # Two pointers on remaining array
        left, right = i + 1, n - 1
        target = -nums[i]
        
        while left < right:
            current_sum = nums[left] + nums[right]
            
            if current_sum == target:
                result.append([nums[i], nums[left], nums[right]])
                
                # Skip duplicates for left
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                
                # Skip duplicates for right
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                
                left += 1
                right -= 1
                
            elif current_sum < target:
                left += 1
            else:
                right -= 1
    
    return result

Why It Works

Structure:

Sort: O(n log n)
Fix first element: Loop i
Two pointers on rest: Find pairs that sum to -nums[i]

Duplicate handling: Skip at three levels (i, left, right).

See detailed explanation: 3Sum duplicates

Optimization Techniques

python

def threeSumOptimized(nums):
    nums.sort()
    result = []
    n = len(nums)
    
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        # Optimization 1: Early termination
        if nums[i] > 0:
            break
        
        # Optimization 2: Skip if minimum possible sum > 0
        if nums[i] + nums[i + 1] + nums[i + 2] > 0:
            break
        
        # Optimization 3: Skip if maximum possible sum < 0
        if nums[i] + nums[n - 2] + nums[n - 1] < 0:
            continue
        
        # Two pointers logic...

Pattern 2: 4Sum (Extending the Pattern)

Problem

Find all unique quadruplets that sum to target.

Complete Solution

python

def fourSum(nums: List[int], target: int) -> List[List[int]]:
    """
    LeetCode #18: 4Sum
    
    Time: O(n³)
    Space: O(1) excluding output
    """
    nums.sort()
    result = []
    n = len(nums)
    
    for i in range(n - 3):
        # Skip duplicates for i
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        # Pruning: minimum possible sum
        if nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target:
            break
        
        # Pruning: maximum possible sum
        if nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target:
            continue
        
        for j in range(i + 1, n - 2):
            # Skip duplicates for j
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue
            
            # Pruning for j
            if nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target:
                break
            
            if nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target:
                continue
            
            # Two pointers on remaining array
            left, right = j + 1, n - 1
            
            while left < right:
                current_sum = nums[i] + nums[j] + nums[left] + nums[right]
                
                if current_sum == target:
                    result.append([nums[i], nums[j], nums[left], nums[right]])
                    
                    # Skip duplicates
                    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 current_sum < target:
                    left += 1
                else:
                    right -= 1
    
    return result

Pattern Structure

Nested loops:

Outer loop: Fix first element (i)
Middle loop: Fix second element (j)
Inner: Two pointers on rest

Duplicate skipping: At each level.

Pruning: Early termination at each level.

Pattern 3: k-Sum Generalization

Recursive Approach

python

def kSum(nums: List[int], target: int, k: int) -> List[List[int]]:
    """
    Generalized k-Sum using recursion.
    
    Time: O(n^(k-1))
    Space: O(k) for recursion stack
    """
    def kSumHelper(start, k, target):
        result = []
        
        # Base case: 2-Sum
        if k == 2:
            left, right = start, len(nums) - 1
            while left < right:
                current_sum = nums[left] + nums[right]
                if current_sum == target:
                    result.append([nums[left], nums[right]])
                    # Skip duplicates
                    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 current_sum < target:
                    left += 1
                else:
                    right -= 1
            return result
        
        # Recursive case: Fix one element, solve (k-1)-Sum
        for i in range(start, len(nums) - k + 1):
            # Skip duplicates
            if i > start and nums[i] == nums[i - 1]:
                continue
            
            # Pruning
            if nums[i] + (k - 1) * nums[-1] < target:
                continue
            if k * nums[i] > target:
                break
            
            # Recursively solve (k-1)-Sum
            sub_results = kSumHelper(i + 1, k - 1, target - nums[i])
            
            # Add current element to each result
            for sub in sub_results:
                result.append([nums[i]] + sub)
        
        return result
    
    nums.sort()
    return kSumHelper(0, k, target)

Usage

python

# 3Sum
result = kSum(nums, 0, 3)

# 4Sum
result = kSum(nums, target, 4)

# 5Sum
result = kSum(nums, target, 5)

Pattern 4: 3Sum Closest

Problem

Find triplet with sum closest to target.

Solution

python

def threeSumClosest(nums: List[int], target: int) -> int:
    """
    LeetCode #16: 3Sum Closest
    
    Time: O(n²)
    Space: O(1)
    """
    nums.sort()
    closest = float('inf')
    n = len(nums)
    
    for i in range(n - 2):
        left, right = i + 1, n - 1
        
        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]
            
            # Update closest
            if abs(current_sum - target) < abs(closest - target):
                closest = current_sum
            
            # Early return if exact match
            if current_sum == target:
                return current_sum
            
            # Move pointers
            if current_sum < target:
                left += 1
            else:
                right -= 1
    
    return closest

Key Difference

3Sum: Find all triplets equal to target.

3Sum Closest: Find single triplet closest to target.

No duplicate handling needed (returning single value, not all combinations).

Pattern 5: 3Sum Smaller

Problem

Count triplets with sum less than target.

Solution

python

def threeSumSmaller(nums: List[int], target: int) -> int:
    """
    LeetCode #259: 3Sum Smaller
    
    Time: O(n²)
    Space: O(1)
    """
    nums.sort()
    count = 0
    n = len(nums)
    
    for i in range(n - 2):
        left, right = i + 1, n - 1
        
        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]
            
            if current_sum < target:
                # All pairs (left, left+1), (left, left+2), ..., (left, right)
                # satisfy the condition
                count += right - left
                left += 1
            else:
                right -= 1
    
    return count

Key Insight

When nums[i] + nums[left] + nums[right] < target:

All pairs (left, j) where left < j <= right also satisfy
Count them all: right - left

Advanced Techniques

Technique 1: Hash Map for 2-Sum Base Case

python

def kSumHashMap(nums, target, k):
    """
    Use hash map for 2-Sum base case (faster for sparse arrays).
    """
    def kSumHelper(start, k, target):
        if k == 2:
            # Hash map approach
            seen = {}
            result = []
            for i in range(start, len(nums)):
                complement = target - nums[i]
                if complement in seen:
                    result.append([complement, nums[i]])
                seen[nums[i]] = i
            return result
        
        # Recursive case...

Technique 2: Bidirectional Pruning

python

def threeSumPruned(nums, target):
    nums.sort()
    result = []
    
    for i in range(len(nums) - 2):
        # Prune from both sides
        min_sum = nums[i] + nums[i + 1] + nums[i + 2]
        if min_sum > target:
            break  # All remaining sums too large
        
        max_sum = nums[i] + nums[-2] + nums[-1]
        if max_sum < target:
            continue  # This i too small
        
        # Two pointers...

Technique 3: Avoiding Overflow

python

def fourSumNoOverflow(nums, target):
    """
    Handle potential integer overflow in sum.
    """
    nums.sort()
    result = []
    
    for i in range(len(nums) - 3):
        for j in range(i + 1, len(nums) - 2):
            left, right = j + 1, len(nums) - 1
            
            while left < right:
                # Avoid overflow by rearranging
                # Instead of: sum == target
                # Use: nums[i] == target - nums[j] - nums[left] - nums[right]
                
                current = nums[left] + nums[right]
                needed = target - nums[i] - nums[j]
                
                if current == needed:
                    result.append([nums[i], nums[j], nums[left], nums[right]])
                    # Skip duplicates...
                elif current < needed:
                    left += 1
                else:
                    right -= 1
    
    return result

Complexity Analysis

Problem	Fixed Elements	Two Pointers	Total Complexity
2-Sum	0	O(n)	O(n)
3-Sum	1 (O(n))	O(n)	O(n²)
4-Sum	2 (O(n²))	O(n)	O(n³)
k-Sum	k-2 (O(n^(k-2)))	O(n)	O(n^(k-1))

Space Complexity: O(1) excluding output, O(k) if using recursion.

Common Mistakes

Mistake 1: Not Skipping Duplicates

python

# WRONG: Generates duplicate triplets
for i in range(len(nums)):
    # No duplicate check!

Fix: Skip duplicates at each level.

Mistake 2: Wrong Duplicate Skip Logic

python

# WRONG
if nums[i] == nums[i - 1]:  # Skips first occurrence!
    continue

Fix: if i > 0 and nums[i] == nums[i - 1]

Mistake 3: Forgetting to Sort

python

# WRONG: Two pointers requires sorted array
for i in range(len(nums)):
    # Two pointers without sorting!

Fix: Always sort first.

Practice Problems

Master multi-pointer with these:

Beginner:

3Sum (#15) - foundation
3Sum Closest (#16) - single result
3Sum Smaller (#259) - counting

Intermediate:
4. 4Sum (#18) - extend to 4 elements
5. 4Sum II (#454) - hash map variant
6. Valid Triangle Number (#611) - similar pattern

Advanced:
7. Subarray Sum Equals K (#560) - prefix sum variant
8. Count of Range Sum (#327) - advanced
9. k-Sum (custom) - generalization

FAQ

Q: Why does k-Sum have O(n^(k-1)) complexity?

A: We fix k-2 elements with nested loops (O(n^(k-2))), then use two pointers (O(n)). Total: O(n^(k-2) × n) = O(n^(k-1)).

Q: Can I use hash map instead?

A: For 2-Sum, yes (O(n) time, O(n) space). For k ≥ 3, two pointers after sorting is usually better.

Q: How do I handle duplicates?

A: Skip adjacent equal values at each loop level. See 3Sum duplicates.

Q: What if target can overflow?

A: Rearrange comparisons to avoid overflow, or use larger integer types.

Conclusion

Advanced multi-pointer techniques extend the two pointers pattern to k elements with systematic approaches.

Key principles:

Fix k-2 elements with nested loops
Two pointers on remaining array
Skip duplicates at each level
Prune for optimization

Complexity:

k-Sum: O(n^(k-1))
Space: O(1) or O(k) with recursion

The pattern:

python

nums.sort()
for i in range(len(nums) - k + 1):
    if i > 0 and nums[i] == nums[i-1]:
        continue
    # Recursively solve (k-1)-Sum

When to use:

Finding k elements that meet condition
Sorted array enables greedy decisions
Need all unique combinations

Master these patterns, and you'll handle any k-Sum problem with confidence. For more patterns, see the complete two pointers guide and sorted arrays.

Next time you see k-Sum, think: fix k-2, two pointers on the rest.

Want to Practice LeetCode Smarter?

LeetCopilot is a free browser extension that enhances your LeetCode practice with AI-powered hints, personalized study notes, and realistic mock interviews — all designed to accelerate your coding interview preparation.

Learn More About LeetCopilot

Add to Chrome for free

Also compatible with Edge, Brave, and Opera

Advanced Two Pointers: 3Sum, 4Sum, and Multi-Pointer Techniques

The Complete Two Pointers Guide: Master All Patterns, Templates, and Techniques

TL;DR

The Multi-Pointer Framework

From 2-Sum to k-Sum

Pattern 1: 3Sum (The Foundation)

Problem

Complete Solution

Why It Works

Optimization Techniques

Pattern 2: 4Sum (Extending the Pattern)

Problem

Complete Solution

Pattern Structure

Pattern 3: k-Sum Generalization

Recursive Approach

Usage

Pattern 4: 3Sum Closest

Problem

Solution

Key Difference

Pattern 5: 3Sum Smaller

Problem

Solution

Key Insight

Advanced Techniques

Technique 1: Hash Map for 2-Sum Base Case

Technique 2: Bidirectional Pruning

Technique 3: Avoiding Overflow

Complexity Analysis

Common Mistakes

Mistake 1: Not Skipping Duplicates

Mistake 2: Wrong Duplicate Skip Logic

Mistake 3: Forgetting to Sort

Practice Problems

FAQ

Conclusion

Want to Practice LeetCode Smarter?

Related Tutorials

Why Your Two Pointers Solution Fails on Unsorted Arrays (And What to Use Instead)

The Off-by-One Trap in Two Pointers: How to Get Pointer Bounds Right Every Time

How to Debug Two Pointers Solutions: Visualization and Common Patterns