Previous
Next
Two Pointers Pattern | From O(n²) to O(n) in Arrays

Two Pointers Pattern | From O(n²) to O(n) in Arrays

· 22분 읽기 · 수정 Intermediate Tutorial
Two Pointers Pattern | From O(n²) to O(n) in Arrays

이 글의 핵심

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)

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)

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

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

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))  # 49

Problem 3: Subarray sum (positive values)

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

The following example demonstrates the concept in 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 while

Interview tips

# Check whether sorting is allowed / needed
# Handle duplicates explicitly when required
# Mind boundaries: left < right vs left <= right

Summary

  1. Two pointers: two indices for O(n) scans.
  2. Patterns: opposite ends, same direction, sliding intervals.
  3. Goal: replace O(n²) brute force where applicable.
  4. Sorting: often O(n log n) preprocessing.

Baekjoon: 2003, 1806
Programmers: Jewelry Shopping
LeetCode: 15. 3Sum, 11. Container With Most Water

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

A. Two pointers algorithm pattern: sorted array pair sums, deduplication, three-sum, and container-with-water—Python exampl… 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.

Q. 선행으로 읽으면 좋은 글은?

A. 각 글 하단의 이전 글 또는 관련 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.

Q. 더 깊이 공부하려면?

A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

이 글에서 다루는 키워드 (관련 검색어)

Algorithm, Two Pointers, Arrays, Coding Interview, Optimization 등으로 검색하시면 이 글이 도움이 됩니다.