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

Frequently Asked Questions (FAQ)

Q. When would I use this in practice?

A. Two pointers algorithm pattern: sorted array pair sums, deduplication, three-sum, and container-with-water—Python exampl…

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.

Other articles related to this topic.

Keywords Covered in This Article (Related Search Terms)

This article covers Algorithm, Two Pointers, Arrays, Coding Interview, Optimization.