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

이 글의 핵심

Master the two pointers technique: two indices scan linearly after sorting or in a single pass—classic optimization from quadratic to linear time on arrays.

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

# 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