python 37 lines · 9 steps

Two-pointer search on sorted arrays

How the two-pointer technique solves two-sum and three-sum on sorted input without nested brute force.

Explained by highlit

Intermediate two-pointers arrays sorting deduplication algorithm-design

1def two_sum_sorted(numbers, target):
  """Find indices of two values that sum to target in a sorted array."""
  left, right = 0, len(numbers) - 1
  while left < right:
      current = numbers[left] + numbers[right]
      if current == target:
          return (left, right)
      elif current < target:
          left += 1
      else:
          right -= 1
  return None
13 
14 
15def three_sum_zero(numbers):
  """Find all unique triplets in a sorted array that sum to zero."""
  result = []
  n = len(numbers)
  for i in range(n - 2):
      if i > 0 and numbers[i] == numbers[i - 1]:
          continue
      left, right = i + 1, n - 1
      while left < right:
          total = numbers[i] + numbers[left] + numbers[right]
          if total == 0:
              result.append((numbers[i], numbers[left], numbers[right]))
              left += 1
              right -= 1
              while left < right and numbers[left] == numbers[left - 1]:
                  left += 1
              while left < right and numbers[right] == numbers[right + 1]:
                  right -= 1
          elif total < 0:
              left += 1
          else:
              right -= 1
  return result

01 / 01

STEP 01

Walkthrough

Space play ←→ step click any line

Three takeaways

1On a sorted array, two pointers converging from both ends find a target pair in linear time instead of quadratic.
2Three-sum reduces to fixing one element and running two-sum on the remainder.
3Skipping equal neighbors after a match is what keeps the triplet results unique.

Related explainers

python

import argparse
import sys
from pathlib import Path

Building a subcommand CLI with argparse

cli argparse subcommands

Intermediate 6 steps

python

from collections.abc import Mapping
from typing import Any, Iterator

Flattening nested config into dotted keys

recursion generators tree-traversal

Intermediate 7 steps

java

public class SortedListMerger {
 
    public static int[] merge(int[] a, int[] b) {
        int[] result = new int[a.length + b.length];

Merging two sorted arrays in Java

two-pointers merging arrays

Beginner 6 steps

python

import csv
import io
from datetime import datetime

Streaming a CSV export in Flask

streaming generators csv

Intermediate 9 steps

python

import time
from collections import defaultdict
from threading import Lock

Sliding-window login rate limiting in Flask

rate-limiting sliding-window thread-safety

Intermediate 7 steps

python

from django.conf import settings
from django.contrib.auth import get_user_model
from django.core.mail import EmailMultiAlternatives
from django.db.models.signals import post_save