Two Pointers on Sorted Arrays: Why Sorting Unlocks O(n) Solutions

You're staring at a problem: "Find all triplets that sum to zero."

Your first instinct: brute force—three nested loops, O(n³). Terrible, but it works.

Then you remember: "What if I sort the array first?"

Suddenly, the problem transforms. With sorting, you can use two pointers and solve it in O(n²). You've just unlocked a massive optimization.

This is the power of sorted arrays. Sorting isn't just about organization—it's about enabling algorithmic techniques that would be impossible otherwise.

This comprehensive guide will teach you why sorting unlocks two pointers, when to sort first, the mathematical proof of correctness, and how to handle the indices vs values trade-off.

TL;DR

Why sorting enables two pointers:

• Monotonicity: Values increase left to right
• Greedy decisions: Can determine which pointer to move
• Proof of correctness: Never miss the optimal solution

When to sort first:

• Finding pairs/triplets (values, not indices)
• Need to avoid duplicates
• Want O(n) or O(n²) instead of O(n²) or O(n³)

Trade-off:

• Time: O(n log n) for sorting + O(n) for two pointers
• Space: O(1) if in-place sort
• Limitation: Loses original indices

Why Sorted Arrays Enable Two Pointers

The Monotonicity Property

Sorted array: arr[i] ≤ arr[i+1] for all i

This simple property unlocks powerful reasoning:

Example: Finding two numbers that sum to target = 9

Sorted: [1, 2, 3, 4, 5, 6, 7, 8]
         L                    R

Sum = 1 + 8 = 9 ✓ Found!

But what if sum was 10?

Sum = 1 + 8 = 9 < 10
Need larger sum → Move L right

Why this works: Because the array is sorted:

• Moving L right guarantees a larger value
• Moving R left guarantees a smaller value

On unsorted arrays, this reasoning breaks down.

The Greedy Decision Framework

Sorted arrays allow greedy decisions based on current values:

if current_sum < target:
    left += 1  # Guaranteed to increase sum
elif current_sum > target:
    right -= 1  # Guaranteed to decrease sum

Proof: See why two pointers fails on unsorted arrays.

Mathematical Proof of Correctness

Claim: Two pointers on a sorted array finds all valid pairs.

Proof:

Suppose optimal pair is at indices (i, j) where i < j.

Case 1: We consider pair (i, j) during execution.

• We find it and return ✓

Case 2: We skip pair (i, j).

This means at some point, we had left ≤ i and right ≥ j, but moved one pointer past the optimal position.

Subcase 2a: We moved left past i.

This happened because arr[left] + arr[right] < target.

Since left < i and array is sorted: arr[left] ≤ arr[i]

Therefore: arr[i] + arr[right] ≥ arr[left] + arr[right] < target

So pair (i, right) also has sum < target.

Since right ≥ j and array is sorted: arr[right] ≥ arr[j]

Therefore: arr[i] + arr[j] ≤ arr[i] + arr[right] < target

Contradiction! Pair (i, j) cannot be optimal if its sum < target.

Subcase 2b: We moved right past j (symmetric argument).

Conclusion: We never skip the optimal pair. ✓

When to Sort First

✅ Sort When:

1. Finding pairs/triplets (values, not indices)
2. Need to avoid duplicates (easier on sorted data)
3. Want O(n) or O(n²) instead of brute force
4. Don't need original indices

❌ Don't Sort When:

1. Need original indices (sorting loses them)
2. Array is already sorted (waste of time)
3. Can't afford O(n log n) (rare)
4. Order matters for the problem logic

Pattern 1: Two Sum (Sort First)

Problem

Find two numbers that sum to target. Return the values, not indices.

Solution

def twoSum(nums: List[int], target: int) -> List[int]:
    """
    Sort first, then use two pointers.
    
    Time: O(n log n) for sort + O(n) for two pointers = O(n log n)
    Space: O(1) if in-place sort
    """
    nums.sort()
    
    left, right = 0, len(nums) - 1
    
    while left < right:
        current_sum = nums[left] + nums[right]
        
        if current_sum == target:
            return [nums[left], nums[right]]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    
    return []

Why Sort?

Without sorting: Would need O(n²) brute force or O(n) hash map (but uses O(n) space).

With sorting: O(n log n) time, O(1) space, and can find all pairs if needed.

Pattern 2: 3Sum (Sort Enables O(n²))

Problem

Find all unique triplets that sum to zero.

Solution

def threeSum(nums: List[int]) -> List[List[int]]:
    """
    Sort first, then fix one element and use two pointers.
    
    Time: O(n log n) + O(n²) = O(n²)
    Space: O(1) excluding output
    """
    nums.sort()
    result = []
    
    for i in range(len(nums) - 2):
        # Skip duplicates for i
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        # Two pointers on remaining array
        left, right = i + 1, len(nums) - 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 and right
                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

Why Sort?

Without sorting:

• O(n³) brute force
• Or complex hash map approach with duplicate handling

With sorting:

• O(n²) with two pointers
• Easy duplicate skipping (adjacent elements)
• Clean, intuitive code

Duplicate handling: See 3Sum duplicates.

Pattern 3: 4Sum (Extends to O(n³))

Solution

def fourSum(nums: List[int], target: int) -> List[List[int]]:
    """
    Sort first, then nested loops + two pointers.
    
    Time: O(n log n) + O(n³) = O(n³)
    Space: O(1) excluding output
    """
    nums.sort()
    result = []
    n = len(nums)
    
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                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]])
                    
                    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 Extension

k-Sum: Can extend to any k with O(n^(k-1)) time.

General pattern:

• Sort: O(n log n)
• Fix k-2 elements: O(n^(k-2))
• Two pointers on rest: O(n)
• Total: O(n^(k-1))

Handling the Indices vs Values Trade-Off

Problem: When You Need Indices

LeetCode #1: Two Sum

• Input: Unsorted array
• Output: Indices of two numbers

Can't sort! Sorting would lose original indices.

Solution: Use hash map instead.

def twoSum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

Solution: Track Indices During Sorting

If you must sort but need indices:

def twoSumWithIndices(nums, target):
    # Create pairs of (value, original_index)
    indexed = [(num, i) for i, num in enumerate(nums)]
    
    # Sort by value
    indexed.sort(key=lambda x: x[0])
    
    left, right = 0, len(indexed) - 1
    
    while left < right:
        current_sum = indexed[left][0] + indexed[right][0]
        
        if current_sum == target:
            return [indexed[left][1], indexed[right][1]]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    
    return []

Trade-off: O(n) extra space to track indices.

Time Complexity Analysis

Sorting Cost

Best sorting algorithms: O(n log n)

• Merge Sort
• Quick Sort (average case)
• Heap Sort

In-place sorts: O(1) space

• Quick Sort
• Heap Sort

Stable sorts: Preserve relative order

• Merge Sort (O(n) space)
• Tim Sort (Python's default)

Total Complexity

Key insight: For k ≥ 3, the two pointers phase dominates, so sorting cost is absorbed.

Advanced Techniques

Technique 1: Early Termination

def threeSum(nums):
    nums.sort()
    result = []
    
    for i in range(len(nums) - 2):
        # Early termination: smallest number is positive
        if nums[i] > 0:
            break  # No way to sum to 0
        
        # Skip duplicates
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        # ... two pointers logic

Technique 2: Pruning

def fourSum(nums, target):
    nums.sort()
    result = []
    n = len(nums)
    
    for i in range(n - 3):
        # 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
        
        # ... rest of logic

Technique 3: Binary Search Hybrid

def threeSumClosest(nums, target):
    """
    Combine sorting + two pointers + binary search for optimization.
    """
    nums.sort()
    closest = float('inf')
    
    for i in range(len(nums) - 2):
        left, right = i + 1, len(nums) - 1
        
        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]
            
            if abs(current_sum - target) < abs(closest - target):
                closest = current_sum
            
            if current_sum < target:
                left += 1
            elif current_sum > target:
                right -= 1
            else:
                return current_sum  # Exact match
    
    return closest

Common Mistakes

Mistake 1: Sorting When Indices Are Required

# WRONG: Problem asks for indices
def twoSum(nums, target):
    nums.sort()  # Loses original indices!
    # ...

Fix: Use hash map or track indices during sorting.

Mistake 2: Not Skipping Duplicates

# WRONG: Generates duplicate triplets
for i in range(len(nums)):
    # No duplicate check!
    # Will process same value multiple times

Fix: Skip duplicates after sorting.

Mistake 3: Sorting Already Sorted Array

# WRONG: Wastes time
def twoSum(nums, target):
    nums.sort()  # nums is already sorted!

Fix: Check if array is sorted first, or read problem statement carefully.

Practice Problems

Master sorting + two pointers with these:

Beginner:

1. Two Sum II (#167) - already sorted
2. 3Sum (#15) - sort first
3. 3Sum Closest (#16) - sort first

Intermediate:
4. 4Sum (#18) - nested loops + two pointers
5. 3Sum Smaller (#259) - count triplets
6. Valid Triangle Number (#611) - sort + two pointers

Advanced:
7. 4Sum II (#454) - hash map variant
8. Subarray Product Less Than K (#713) - sliding window on sorted
9. Count of Range Sum (#327) - advanced sorting

FAQ

Q: When should I sort first?

A: When you need pairs/triplets (values, not indices), want to avoid duplicates, and can afford O(n log n) time.

Q: What if I need original indices?

A: Use hash map instead, or track indices during sorting with extra O(n) space.

Q: Is sorting always worth it?

A: For k-Sum where k ≥ 3, yes. For Two Sum, hash map is often simpler (O(n) time, O(n) space).

Q: How do I handle duplicates?

A: After sorting, skip adjacent equal values. See 3Sum duplicates.

Q: Can I use two pointers without sorting?

A: Yes, for in-place manipulation (Move Zeroes, Remove Duplicates) or if array is already sorted. See in-place manipulation.

Conclusion

Sorting unlocks the two pointers technique by providing the monotonicity needed for greedy decisions.

Key insights:

• Monotonicity enables greedy pointer movement
• Proof of correctness guarantees we don't miss solutions
• Duplicate handling is trivial on sorted data
• Time complexity is dominated by two pointers phase for k ≥ 3

When to sort:

• Finding pairs/triplets (values, not indices)
• Avoiding duplicates
• Want O(n²) instead of O(n³)

Trade-offs:

• Time: O(n log n) for sorting
• Space: O(1) if in-place
• Limitation: Loses original indices

The pattern:

nums.sort()  # O(n log n)

for i in range(len(nums)):
    left, right = i + 1, len(nums) - 1
    while left < right:
        # Two pointers logic

Master this pattern, and you'll transform cubic problems into quadratic ones. For more patterns, see the complete two pointers guide and opposite direction template.

Next time you see a k-Sum problem, your first thought should be: "Sort first, then two pointers."