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):
2 """Find indices of two values that sum to target in a sorted array."""
3 left, right = 0, len(numbers) - 1
4 while left < right:
5 current = numbers[left] + numbers[right]
6 if current == target:
7 return (left, right)
8 elif current < target:
9 left += 1
10 else:
11 right -= 1
12 return None
13 
14 
15def three_sum_zero(numbers):
16 """Find all unique triplets in a sorted array that sum to zero."""
17 result = []
18 n = len(numbers)
19 for i in range(n - 2):
20 if i > 0 and numbers[i] == numbers[i - 1]:
21 continue
22 left, right = i + 1, n - 1
23 while left < right:
24 total = numbers[i] + numbers[left] + numbers[right]
25 if total == 0:
26 result.append((numbers[i], numbers[left], numbers[right]))
27 left += 1
28 right -= 1
29 while left < right and numbers[left] == numbers[left - 1]:
30 left += 1
31 while left < right and numbers[right] == numbers[right + 1]:
32 right -= 1
33 elif total < 0:
34 left += 1
35 else:
36 right -= 1
37 return result
01 / 01
STEP 01

Walkthrough

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

Related explainers

python 
from fastapi import APIRouter, BackgroundTasks, Depends, HTTPException, status
from pydantic import BaseModel, EmailStr
from sqlalchemy.orm import Session
 

Building a signup endpoint in FastAPI

dependency-injection request-validation background-tasks
Intermediate 8 steps
python 
from django import forms
from django.utils import timezone
 
from .models import Reservation

Multi-field validation in a Django ModelForm

form validation cross-field validation modelform
Intermediate 7 steps
python 
from django import template
from django.urls import reverse, NoReverseMatch
from django.utils.html import format_html
 

Active nav-link template tags in Django

template tags url routing active state
Intermediate 7 steps
python 
from functools import wraps
import asyncio
 
from fastapi import APIRouter, FastAPI, Request

Per-route request timeouts in FastAPI

decorators async timeouts
Intermediate 6 steps
python 
import os
from pathlib import Path
 
BASE_DIR = Path(__file__).resolve().parent.parent.parent

How a Django settings module is wired

configuration environment-variables middleware
Intermediate 8 steps
python 
def is_valid_card_number(number: str) -> bool:
    digits = [int(c) for c in number if c.isdigit()]
 
    if len(digits) < 13 or len(digits) > 19:

Validating card numbers with the Luhn check

checksum validation luhn-algorithm
Intermediate 6 steps

Share this explainer

Here's the card — post it anywhere.

Two-pointer search on sorted arrays — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code