Skip to content

Volume ITechnology

4.5.2 — Two Sum II: Input Array Is Sorted ​

LeetCode 167 · Medium

The problem ​

You are given a list of numbers called numbers, sorted from smallest to largest, and a number target. Find the two numbers that add up to target. Return their positions, counting from 1, not from 0.

numbers = [2, 7, 11, 15], target = 9   →  [1, 2]    (2 + 7 = 9)
numbers = [2, 3, 4],      target = 6   →  [1, 3]    (2 + 4 = 6)
numbers = [-1, 0],        target = -1  →  [1, 2]    (-1 + 0 = -1)

The list has up to 30,000 numbers, and they can be negative. Exactly one answer exists. You must use only O(1) extra memory, meaning a fixed handful of variables, no matter how long the list is.

What the problem is really asking ​

This is 4.4.3 Two Sum with two changes. The list is sorted, which is a gift. And the memory limit rules out the hash map that solved Two Sum, since a map grows with the list.

So the question is: how can the sorted order replace the hash map?

The brute force, and where it wastes work ​

Try every pair.

python
def twoSum(numbers, target):
    n = len(numbers)
    for i in range(n):
        for j in range(i + 1, n):
            if numbers[i] + numbers[j] == target:
                return [i + 1, j + 1]

That is about \frac{n^2}{2} pairs, which for 30,000 numbers is 450 million checks. Too slow.

The waste in one sentence: it completely ignores that the list is sorted, so it cannot tell which pairs are hopeless without checking each one.

The idea ​

Put one pointer on the smallest number, at the left end, and one on the largest, at the right end. Add the two numbers.

  • The sum is too small. We need a bigger sum. The only way to get one is to move the left pointer one step right, onto a larger number.
  • The sum is too big. We need a smaller sum. Move the right pointer one step left, onto a smaller number.
  • The sum is exactly right. Done.

Think of a see-saw with a row of children lined up by weight. You put the lightest child on one end and the heaviest on the other. If the heavy side wins, you swap in the next lighter child on that side. If the light side is up in the air, you swap in the next heavier child on the light side. Because the children are lined up by weight, the see-saw always tells you which side to change.

Why throwing a number away is safe ​

We go slowly here, because every two-pointer solution in this chapter rests on this one argument.

Suppose numbers[l] + numbers[r] is less than the target. Ask: "what could numbers[l] still pair with?" Its biggest possible partner is numbers[r], because the list is sorted and r is the far end of what is left. Even with that biggest partner, the sum is too small. So numbers[l] cannot reach the target with any remaining number. It can never be part of the answer. We can throw it away for good by moving l right.

The same argument works the other way. If the sum is too big, the smallest possible partner for numbers[r] is numbers[l]. Even that is too big. So numbers[r] can never be part of the answer, and we throw it away by moving r left.

So every move throws away one number that has been proved useless. No move ever needs to be undone.

This argument, "this number cannot be part of any answer, so dropping it is safe", is the proof behind every two-pointer solution. If you cannot make that argument for a problem, two pointers is the wrong tool for it.

The solution ​

python
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l, r = 0, len(numbers) - 1              # (1)
        while l < r:                            # (2)
            total = numbers[l] + numbers[r]     # (3)
            if total == target:                 # (4)
                return [l + 1, r + 1]
            if total < target:                  # (5)
                l += 1
            else:                               # (6)
                r -= 1
        return []                               # (7)
ts
function twoSum(numbers: number[], target: number): number[] {
  let l = 0, r = numbers.length - 1;            // (1)
  while (l < r) {                               // (2)
    const total = numbers[l] + numbers[r];      // (3)
    if (total === target) return [l + 1, r + 1];  // (4)
    if (total < target) l++;                    // (5)
    else r--;                                   // (6)
  }
  return [];                                    // (7)
}

Line by line ​

(1) Start at the two ends. l points at the smallest number and r at the largest. Starting anywhere else would break the argument above, because we would not know that numbers[r] is the biggest partner left for numbers[l].

(2) Loop while l < r. We need two different positions. If l and r met, we would be adding a number to itself.

(3) Add the two numbers.

(4) Found it. Return both positions with 1 added to each, because the problem counts from 1. This + 1 is the most common slip on this problem.

(5) Too small, so drop the left number. Even the biggest partner was not enough, so numbers[l] is useless. Move l right.

(6) Too big, so drop the right number. Even the smallest partner was too much, so numbers[r] is useless. Move r left.

(7) A fallback. The problem promises an answer, so this never runs. It is there so the function always returns a list.

Trace ​

Take numbers = [2, 7, 11, 15] and target = 9.

Stepl (value)r (value)SumCompared with 9Action
10 (2)3 (15)17too bigdrop 15, r → 2
20 (2)2 (11)13too bigdrop 11, r → 1
30 (2)1 (7)9equalreturn [1, 2]

At step 1, 15 is dropped. Is that safe? The smallest partner 15 could have is 2, and 2 + 15 = 17 is already too big. So 15 can never be in the answer. The same reasoning drops 11 at step 2.

Complexity, derived ​

Time. Each turn of the loop moves exactly one pointer by one step: l goes right or r goes left. The pointers start n - 1 positions apart, and the loop stops when they meet. So there are at most n - 1 turns. Each turn does one addition and one or two comparisons, which is constant work. So the time is O(n).

Space. We keep three numbers: l, r and total. That does not grow with the list. So the extra memory is O(1), which meets the rule.

You could also solve this with binary search: for each number, search the sorted list for its partner, which takes O(\log n) per search. That is O(n \log n) in total. Two pointers is faster, because each step reuses what the last comparison taught us instead of starting a fresh search.

Edge cases ​

  • Negative numbers, such as [-5, -2, 3] with target −2. The pointer rules still work, because the list is sorted. Moving right always gives a bigger number, even among negatives. Here -5 + 3 = -2 on the first step.
  • Equal values, such as [3, 3, 4] with target 6. Step 1: 3 + 4 = 7, too big, drop the 4. Step 2: 3 + 3 = 6, found, return [1, 2].
  • The answer is the two ends. Found on the first step.

Two pointers or a hash map? ​

If the input is sorted, use two pointers. It needs no extra memory.

If the input is unsorted and you must return the original positions, use a hash map, as in Two Sum. Sorting would move the numbers and lose their positions.

If the input is unsorted but you only need the values, and memory is tight, you can sort first and then use two pointers.

Variations you will meet ​

  • 3Sum. Find three numbers that add to zero. Fix the first number, then run this exact loop on the numbers after it. That is the next page, 4.5.3.
  • 4Sum. Fix two numbers, then run this loop.
  • Two Sum Less Than K. Find the largest sum that is still below k. Same pointer moves, but you record the best sum each time it is below k.

What the interviewer will push on ​

"Why not use a hash map, like Two Sum?" They want the memory reason. A map uses O(n) extra memory. The sorted order lets two pointers do it in O(1).

"Prove that moving the left pointer is safe." They are checking the argument, not the code. The biggest partner left for numbers[l] is numbers[r], and even that was too small, so numbers[l] can never be part of the answer.

"What if there were many answers, and you had to return all of them?" Do not return on a match. Record the pair, move both pointers inward, and skip over equal neighbours so the same pair of values is not recorded twice.

"What if the list were sorted from largest to smallest?" Swap the two moves, or start l at the right end and r at the left. The logic is the same, mirrored.

One thing to volunteer: state the "this number can never be part of the answer" argument before you code. It is the proof that makes every two-pointer solution correct.

Next: 4.5.3 3Sum. This loop wrapped inside another loop, where the real difficulty turns out to be skipping duplicates.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet