FAANG · LeetCode #167

Two Sum II — Sorted Array — three-stage drill

1The ProblemMedium

Two Sum II — Sorted Array

Find two numbers in a sorted array that add up to a target.

Examples

[1,3,4,5,7,11], t=9→ [3,4][1,3,4,5], t=20→ []

2The PatternTIME O(n) · SPACE O(1)

Two Pointers

Converging from both ends, comparing as they meet.

Problems using this pattern

3The SolutionRESULT → [3, 4]

Step through it

Initialize: left at 0, right at 5. target = 9.

Step 1 / 6

Python▎two pointers converge

1def twoSum(numbers, target):
2    left, right = 0, len(numbers) - 1
3    while left < right:
4        total = numbers[left] + numbers[right]
5        if total == target:
6            return [left + 1, right + 1]
7        if total < target:
8            left += 1
9        else:
10            right -= 1
11    return []

Arrow keys to navigate · escape to reset

All problems by pattern

Two Pointers

Sliding Window

Prefix Sum

Monotonic Deque

Shortest Subarray with Sum at Least K

Binary Search

Arrays & Hashing

Monotonic Stack

Intervals

Two Sum II — Sorted Array — three-stage drill

Two Sum II — Sorted Array

Two Pointers

Step through it

All problems by pattern

Two Pointers

Sliding Window

Prefix Sum

Monotonic Deque

Binary Search

Arrays & Hashing

Monotonic Stack

Intervals

Heap / Top-K

Backtracking

Recursive Descent