Two Pointers | O → O Optimization Technique Complete Guide
이 글의 핵심
Master two pointers technique: O(n²) → O(n) optimization. Learn basic patterns, practical problems with principles, code examples, and coding interview tips.
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)) # 49Why 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 resultProblem 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 += 1When 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")) # TruePartition 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) # 2Practical 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 elementsCommon 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 -= 1Summary
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 |
Recommended Problems
Baekjoon
LeetCode
- LeetCode 1: Two Sum
- LeetCode 15: 3Sum
- LeetCode 11: Container With Most Water
- LeetCode 26: Remove Duplicates from Sorted Array
- LeetCode 125: Valid Palindrome
Programmers
Related Posts
- Greedy Algorithm | “Best Choice Every Step” Complete Guide
- Algorithm Series Full Index
- Arrays and Lists
- Stack and Queue
Keywords
Two Pointers, Algorithm, Optimization, Two Sum, Three Sum, Subarray, Coding Interview, O(n), Sorted Array, Fast and Slow Pointers
Frequently Asked Questions (FAQ)
Q. When would I use this in practice?
A. Master two pointers technique: O(n²) → O(n) optimization. Learn basic patterns, practical problems with principles, code…
Q. What should I read before this?
A. Follow the previous article or related articles links at the bottom of each post to learn in sequence.
Q. Where can I study this more deeply?
A. Check cppreference and the relevant library’s official documentation. The reference links at the end of the article are also worth using.
Related Articles (Internal Links)
Other articles related to this topic.
- 슬라이딩 윈도우 | 부분 배열 최적화 기법 완벽 정리
- 배열과 리스트 | 코딩 테스트 필수 자료구조 완벽 정리
- Greedy Algorithm | Best Choice Every Step Complete Guide
Keywords Covered in This Article (Related Search Terms)
This article covers Algorithm, Two Pointers, Optimization, Coding Interview.