[2026] Two Pointers Pattern | From O(n²) to O(n) in Arrays
![[2026] Two Pointers Pattern | From O(n²) to O(n) in Arrays](/og/s/algorithm-two-pointers-pattern-en.webp)
이 글의 핵심
Two pointers algorithm pattern: sorted array pair sums, deduplication, three-sum, and container-with-water—Python examples and complexity notes for coding interviews.
Introduction
The two pointers technique uses two indices to scan an array efficiently—often reducing O(n²) brute force to O(n) after sorting or in a single linear pass.
1. Two pointers basics
Pattern A: both ends (usually needs sorted data)
다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
def two_sum_sorted(arr, target):
"""
In a sorted array, find two indices whose values 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
else:
right -= 1
return []
# Test
arr = [1, 2, 3, 4, 6]
print(two_sum_sorted(arr, 6)) # [1, 3] (2+4=6)Pattern B: same direction (read/write)
다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
def remove_duplicates(arr):
"""
Remove duplicates from a sorted array in-place; return new length.
"""
if not arr:
return 0
write = 1
for read in range(1, len(arr)):
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]2. Practice problems
Problem 1: 3Sum
다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
def three_sum(arr):
"""
Find triples 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):
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]])
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))Problem 2: Container with most water
다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
def max_area(heights):
"""
Max water trapped between two vertical 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)
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)) # 49Problem 3: Subarray sum (positive values)
다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
def subarray_sum(arr, target):
"""
Count contiguous subarrays whose sum equals target (positive array).
"""
left = 0
current_sum = 0
count = 0
for right in range(len(arr)):
current_sum += arr[right]
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. Pattern summary
아래 코드는 python를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
# 1. Two ends (often sorted)
left, right = 0, len(arr) - 1
while left < right:
# move left or right by the rule
# 2. Same direction (fast & slow)
slow = 0
for fast in range(len(arr)):
# advance slow when condition holds
# 3. Interval expansion
left = 0
for right in range(len(arr)):
# maintain [left, right] with inner whileInterview tips
# Check whether sorting is allowed / needed
# Handle duplicates explicitly when required
# Mind boundaries: left < right vs left <= rightSummary
- Two pointers: two indices for O(n) scans.
- Patterns: opposite ends, same direction, sliding intervals.
- Goal: replace O(n²) brute force where applicable.
- Sorting: often O(n log n) preprocessing.