When to use two pointers?

Use for finding two numbers in sorted array, finding subarrays, etc. Optimizes O(n²) → O(n).

Difference from sliding window?

Two pointers move based on conditions, sliding window moves with fixed size.

Works on unsorted arrays?

Possible but usually used after sorting. Sorting cost is O(n log n).

Two Pointers | O(n²) → O(n) Optimization Technique Complete Guide

2026년 3월 28일 · 22분 읽기 · 수정 2026년 3월 30일 Intermediate Tutorial

이 글의 핵심

Practical guide to two pointers technique. Complete coverage of O(n²) → O(n) optimization with detailed examples.

Introduction

”Two Pointers: O(n²) → O(n)”

Two pointers is a technique that uses two indices to efficiently traverse an array.

1. Two Pointers Basics

Pattern 1: Start from Both Ends

def two_sum_sorted(arr, target):
    """
    Find two numbers in sorted array that sum to target
    """
    left, right = 0, len(arr) - 1
    
    while left < right:
        current_sum = arr[left] + arr[right]
        
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1  # Increase sum
        else:
            right -= 1  # Decrease sum
    
    return []

# Test
arr = [1, 2, 3, 4, 6]
print(two_sum_sorted(arr, 6))  # [1, 3] (2+4=6)

Why O(n)?

Naive approach (nested loops):
for i in range(n):
    for j in range(i+1, n):
        if arr[i] + arr[j] == target:
            return [i, j]
Time: O(n²)

Two pointers:
left, right = 0, n-1
while left < right:
    # Move one pointer per iteration
Time: O(n)

Pattern 2: Same Direction (Fast & Slow)

def remove_duplicates(arr):
    """
    Remove duplicates in sorted array (in-place)
    """
    if not arr:
        return 0
    
    write = 1  # Write pointer
    
    for read in range(1, len(arr)):  # Read pointer
        if arr[read] != arr[read - 1]:
            arr[write] = arr[read]
            write += 1
    
    return write

# Test
arr = [1, 1, 2, 2, 3, 4, 4]
length = remove_duplicates(arr)
print(arr[:length])  # [1, 2, 3, 4]

How It Works:

arr = [1, 1, 2, 2, 3, 4, 4]

Initial: write=1, read=1
Step 1: read=1, arr[1]=1 (duplicate, skip)
Step 2: read=2, arr[2]=2 (new, write), write=2
Step 3: read=3, arr[3]=2 (duplicate, skip)
Step 4: read=4, arr[4]=3 (new, write), write=3
Step 5: read=5, arr[5]=4 (new, write), write=4
Step 6: read=6, arr[6]=4 (duplicate, skip)

Result: [1, 2, 3, 4]

2. Practical Problems

Problem 1: Three Sum

def three_sum(arr):
    """
    Find three numbers that sum to 0
    [-1, 0, 1, 2, -1, -4] → [[-1, -1, 2], [-1, 0, 1]]
    """
    arr.sort()
    result = []
    
    for i in range(len(arr) - 2):
        # Skip duplicates
        if i > 0 and arr[i] == arr[i - 1]:
            continue
        
        left, right = i + 1, len(arr) - 1
        
        while left < right:
            total = arr[i] + arr[left] + arr[right]
            
            if total == 0:
                result.append([arr[i], arr[left], arr[right]])
                
                # Skip duplicates
                while left < right and arr[left] == arr[left + 1]:
                    left += 1
                while left < right and arr[right] == arr[right - 1]:
                    right -= 1
                
                left += 1
                right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1
    
    return result

# Test
arr = [-1, 0, 1, 2, -1, -4]
print(three_sum(arr))
# [[-1, -1, 2], [-1, 0, 1]]

Step-by-Step Trace:

arr = [-4, -1, -1, 0, 1, 2] (sorted)

i=0, arr[i]=-4:
  left=1(-1), right=5(2): -4-1+2=-3 (< 0, left++)
  left=2(-1), right=5(2): -4-1+2=-3 (< 0, left++)
  left=3(0), right=5(2): -4+0+2=-2 (< 0, left++)
  left=4(1), right=5(2): -4+1+2=-1 (< 0, left++)
  left=5, right=5: stop

i=1, arr[i]=-1:
  left=2(-1), right=5(2): -1-1+2=0 ✅ → [-1,-1,2]
  left=3(0), right=4(1): -1+0+1=0 ✅ → [-1,0,1]

i=2, arr[i]=-1: skip (duplicate)

Problem 2: Container With Most Water

def max_area(heights):
    """
    Maximum water between two lines
    """
    left, right = 0, len(heights) - 1
    max_water = 0
    
    while left < right:
        width = right - left
        height = min(heights[left], heights[right])
        water = width * height
        max_water = max(max_water, water)
        
        # Move shorter side
        if heights[left] < heights[right]:
            left += 1
        else:
            right -= 1
    
    return max_water

# Test
heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]
print(max_area(heights))  # 49

Why Move Shorter Side?

heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]
          L                       R

Current: width=8, height=min(1,7)=1, water=8*1=8

If move right (R--):
  width=7, height=min(1,3)=1, water=7*1=7 (worse)

If move left (L++):
  width=7, height=min(8,7)=7, water=7*7=49 (better!)

Lesson: Moving taller side never improves result

Problem 3: Subarray Sum

def subarray_sum(arr, target):
    """
    Count subarrays with sum equal to target (positive array)
    """
    left = 0
    current_sum = 0
    count = 0
    
    for right in range(len(arr)):
        current_sum += arr[right]
        
        # If sum > target, move left
        while current_sum > target and left <= right:
            current_sum -= arr[left]
            left += 1
        
        if current_sum == target:
            count += 1
    
    return count

# Test
arr = [1, 2, 3, 4, 5]
print(subarray_sum(arr, 5))  # 2 ([2,3], [5])

3. Two Pointers Patterns

Pattern Summary

# 1. Start from both ends (sorting required)
left, right = 0, len(arr) - 1
while left < right:
    # Move left++ or right-- based on condition

# 2. Same direction (fast & slow)
slow = 0
for fast in range(len(arr)):
    # Move slow++ when condition met

# 3. Range search
left = 0
for right in range(len(arr)):
    # Process range [left, right]
    while condition:
        left += 1

When to Use Each Pattern

Pattern	Use Case	Example
Both ends	Two sum, palindrome	Sorted array search
Same direction	Remove duplicates, partition	In-place modification
Range search	Subarray sum, substring	Variable-length window

4. Advanced Techniques

Palindrome Check

def is_palindrome(s):
    """
    Check if string is palindrome (ignore non-alphanumeric)
    """
    left, right = 0, len(s) - 1
    
    while left < right:
        # Skip non-alphanumeric
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        
        if s[left].lower() != s[right].lower():
            return False
        
        left += 1
        right -= 1
    
    return True

# Test
print(is_palindrome("A man, a plan, a canal: Panama"))  # True

Partition Array

def partition(arr, pivot):
    """
    Partition array around pivot
    [3,1,4,2,5], pivot=3 → [1,2,3,4,5]
    """
    left = 0
    
    for right in range(len(arr)):
        if arr[right] < pivot:
            arr[left], arr[right] = arr[right], arr[left]
            left += 1
    
    return left

# Test
arr = [3, 1, 4, 2, 5]
pivot_idx = partition(arr, 3)
print(arr)  # [1, 2, 3, 4, 5]
print(pivot_idx)  # 2

Practical Tips

Coding Interview Tips

# ✅ Check if sorted
# Sort first if not sorted

# ✅ Handle duplicates
# Add logic to skip same values

# ✅ Boundary conditions
# Be careful with left < right vs left <= right

# ✅ Edge cases
# - Empty array
# - Single element
# - All same elements

Common Mistakes

# ❌ Wrong: Forgot to sort
arr = [3, 1, 4, 2, 5]
two_sum_sorted(arr, 6)  # Wrong result!

# ✅ Correct: Sort first
arr.sort()
two_sum_sorted(arr, 6)

# ❌ Wrong: Infinite loop
while left < right:
    if condition:
        # Forgot to move pointers!
        pass

# ✅ Correct: Always move pointers
while left < right:
    if condition:
        left += 1
    else:
        right -= 1

Summary

Key Points

Two Pointers: Use two indices for O(n) traversal
Patterns: Both ends, same direction, range search
Optimization: O(n²) → O(n)
Sorting: Usually used after sorting

Pattern Checklist

Pattern	Movement	Condition	Example
Both ends	left++, right—	Compare sum	Two sum
Same direction	slow++, fast++	Compare values	Remove duplicates
Range search	left++, right++	Window condition	Subarray sum

Keywords

Two Pointers, Algorithm, Optimization, Two Sum, Three Sum, Subarray, Coding Interview, O(n), Sorted Array, Fast and Slow Pointers

Two Pointers | O(n²) → O(n) Optimization Technique Complete Guide

이 글의 핵심

Introduction

”Two Pointers: O(n²) → O(n)”

1. Two Pointers Basics

Pattern 1: Start from Both Ends

Pattern 2: Same Direction (Fast & Slow)

2. Practical Problems

Problem 1: Three Sum

Problem 2: Container With Most Water

Problem 3: Subarray Sum

3. Two Pointers Patterns

Pattern Summary

When to Use Each Pattern

4. Advanced Techniques

Palindrome Check

Partition Array

Practical Tips

Coding Interview Tips

Common Mistakes

Summary

Key Points

Pattern Checklist

Recommended Problems

Baekjoon

LeetCode

Programmers

Keywords

이 글의 핵심

Introduction

”Two Pointers: O(n²) → O(n)”

1. Two Pointers Basics

Pattern 1: Start from Both Ends

Pattern 2: Same Direction (Fast & Slow)

2. Practical Problems

Problem 1: Three Sum

Problem 2: Container With Most Water

Problem 3: Subarray Sum

3. Two Pointers Patterns

Pattern Summary

When to Use Each Pattern

4. Advanced Techniques

Palindrome Check

Partition Array

Practical Tips

Coding Interview Tips

Common Mistakes

Summary

Key Points

Pattern Checklist

Recommended Problems

Baekjoon

LeetCode

Programmers

Related Posts

Keywords