TRT
Sign in

Advanced · Module 14 · Lesson 1 of 4

Two pointers

On a sorted array, two indexes moving toward each other can find pairs with a given sum in one pass, because every move rules out a whole row of candidate pairs. The same argument powers three-sum, container problems and trapping rain water.

Pro — members onlyAbout 14 minutes

By the end you can

  • Find a pair with a given sum in a sorted array in O(n) with converging pointers
  • Explain why each pointer move is safe, in terms of the pairs it rules out
  • Extend the pattern to three-sum and to problems where the pointer that moves is the limiting one

Builds on Two pointers on arrays, Merge sort.

01 · A question first

Find two numbers in a sorted array of a million that add up to a target. Checking every pair means about half a trillion additions. Two pointers moving toward each other need at most a million steps. Why is it safe to skip all the other pairs without ever looking at them?

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

  • A pattern that skips work safely
  • Pairs with a given sum
  • Three sum
  • When the limiting side moves
  • When to reach for it
  • Pseudocode & Multi-Language Implementations (C++, Java, Python)
  • Complexity Derivation, Edge Cases & Common Mistakes
See plansAlready a member? Sign in

03 · Practice

Practice · medium · LeetCodeTwo sum II: input array is sortedFind two numbers in a sorted array that add up to a target, in O(n) time and O(1) space, with converging pointers.Practice · medium · LeetCode3SumFind every unique triple that sums to zero by fixing one value and running a two-pointer scan on the rest.Practice · medium · LeetCodeContainer with most waterFind two lines that hold the most water, moving the pointer at the shorter line inward each step.Practice · hard · LeetCodeTrapping rain waterCompute the water trapped between bars after rain, with two pointers and running maximums from each side.

Asked in interviews

Something wrong with this lesson? Report a problem