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

php 
<?php
 
class NameParser
{

Parsing a full name into components in PHP

string-parsing arrays normalization
Intermediate 8 steps
python 
from fastapi import FastAPI, WebSocket, WebSocketDisconnect
 
app = FastAPI()
 

Building a WebSocket chat with FastAPI

websockets broadcast connection-management
Intermediate 9 steps
python 
import time
import uuid
 
from django.utils.deprecation import MiddlewareMixin

Attaching per-request context in Django

middleware request lifecycle multi-tenancy
Intermediate 7 steps
python 
import random
from typing import Iterator, List
 
 

How reservoir sampling picks k items

reservoir-sampling streaming randomness
Intermediate 5 steps
go 
package logging
 
import (
	"context"

Deduplicating log attributes in Go's slog

decorator-pattern structured-logging immutability
Intermediate 8 steps
python 
import secrets
 
from django.contrib.auth import authenticate, login
from django.core.cache import cache

Two-factor login with OTP in Django

two-factor-auth one-time-passwords caching
Intermediate 9 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