Two Sum
The hash map is optimal for exactly one problem in this family. Every later one either hands you a property that makes the map unnecessary (sorted input) or asks for something the map can't give (every distinct tuple).
At each step, ask two things: what does the input let me assume, and what shape is the answer?
Unsorted input, so pay for a hash map
The array is unsorted, so nothing tells you where a complement lives. You pay O(N) memory for an O(1) lookup. The three solutions below sit at three points on that trade: O(N2) time with no memory, two passes, or one pass.
1. Two Sum
Brute Force
Duplicates, collisions, and when sorting wins
Duplicates overwrite, collisions crowd: only crowding hurts. A duplicate key overwrites its own entry in O(1). A collision is two different keys in one bucket; enough of them make every operation O(n). Say it as: "Expected O(n), worst O(n2) under adversarial collisions."
When sorting beats the map. The map is O(n) expected. With adversarial collisions every lookup costs O(n), so its worst case is O(n2). Sorting guarantees O(n log n), the best worst case available here. The catch: LeetCode 1 returns original indices and sorting scrambles them, so sort (value, index) pairs (O(n) extra space), then run two pointers. Once the input arrives sorted (167), the sort is free and the map loses outright.
Sorted input replaces the hash map
Sum too high: move the right pointer in. Sum too low: move the left pointer out. One pass, nothing stored. Two Sum's hash map still works, but it spends O(N) memory to rebuild an order the input already gave you. Say that out loud in the interview.
167. Two Sum II - Input Array Is Sorted
2 Converging Pointers
Borrowed from Two Pointers ↗The approach ladder
| Approach | Time | When you say it |
|---|---|---|
| Aux space | ||
| Brute Force | O(n2) | opening line only |
| O(1) | ||
| 1-Pass Index Map (from 1) | O(n) expected | ignores the sort |
| O(n) | ||
| Fix One, Bisect Another | O(n log n) | lopsided sizes or many queries |
| O(1) | ||
| 2 Converging Pointers | O(n) | the expected answer |
| O(1) |
Pairs less than target
Sorted input lets the scan count without listing. When nums[left] + nums[right]
is under the target, every index between left and right also pairs with
left, so one comparison counts a whole range.
2824. Count Pairs Whose Sum is Less than Target
Brute Force
Every approach
| Approach | Time | When an interviewer wants it |
|---|---|---|
| Aux space | ||
| Brute Force | O(n2) | opening line |
| O(1) | ||
Sort + Bisect per i | O(n log n) | "without two pointers" |
| O(sort) | ||
| Sort + 2 Converging Pointers | O(n log n) | the expected answer |
| O(sort) | ||
| Count by Value | O(n + V2) | when the tiny value range is the point |
| O(V) |
Same scan as 2824, but keep the largest sum under k instead of a count.
1099. Two Sum Less Than K
Given an array nums of integers and an integer k, return the maximum sum such that there exists i < j with nums[i] + nums[j] = sum and sum < k. If no i, j exist satisfying this equation, return -1.
nums = [34, 23, 1, 24, 75, 33, 54, 8],k = 60returns58:34 + 24.nums = [10, 20, 30],k = 15returns-1: no pair sums below 15.- Constraints:
1 <= nums.length <= 100,1 <= nums[i] <= 1000,1 <= k <= 2000.
Brute Force
Every approach
| Approach | Time | When an interviewer wants it |
|---|---|---|
| Aux space | ||
| Brute Force | O(n2) | opening line |
| O(1) | ||
| Sort + Fix One, Bisect Another | O(n log n) | "without two pointers" |
| O(sort) | ||
| Sort + 2 Converging Pointers | O(n log n) | the expected answer |
| O(sort) | ||
| Count by Value | O(n + D2) | when the small value range is the point |
| O(D) |
Pairs in a range
One count can only enforce one bound. Count the pairs up to each bound and subtract: it is 2824's scan run twice.
2563. Count the Number of Fair Pairs
Given a 0-indexed integer array nums of size n and two integers lower and upper, return the number of fair pairs. A pair (i, j) is fair if 0 <= i < j < n and lower <= nums[i] + nums[j] <= upper.
nums = [0, 1, 7, 4, 4, 5],lower = 3,upper = 6returns6: pairs(0, 3),(0, 4),(0, 5),(1, 3),(1, 4)and(1, 5).nums = [1, 7, 9, 2, 5],lower = 11,upper = 11returns1: pair(2, 3).- Constraints:
1 <= nums.length <= 105,-109 <= nums[i] <= 109,-109 <= lower <= upper <= 109.
Brute Force
Every approach
| Approach | Time | When an interviewer wants it |
|---|---|---|
| Aux space | ||
| Brute Force | O(n2) | opening line |
| O(1) | ||
| Sort + Count Twice | O(n log n) | the expected answer |
| O(sort) |
Every distinct triplet
The answer is every distinct triple, so you can't return on the first match. The hard part moves from finding a complement to not reporting the same triple twice, and a map keyed by value has no order to dedupe with.
Sort the array, fix the outer index (or two), and run 167's two-pointer scan on the rest, skipping equal neighbours as you go. 3Sum is 167 inside one loop; 4Sum is 167 inside two.
4Sum comes after the 3Sum family below.
15. 3Sum
Brute Force
Not reporting a triplet twice
- After a match, move both pointers, then step each past values equal to the one just used.
- Skip
iwhennums[i]equals the previous fixed value. - Sorted, so
breakoncenums[i] > 0: no sum can reach 0.
Every 3Sum approach is an earlier one
| Approach | Built from | Time |
|---|---|---|
| Aux space | ||
| Brute Force | sorted-tuple set | O(n3) |
| O(T) | ||
| Sort + Fix Two, Bisect the Third | 167: Fix One, Bisect Another | O(n2 log n) |
| O(sort) | ||
| Fix One + 1-Pass Index Map | 1: 1-Pass Index Map | O(n2) expected |
| O(n) | ||
| Sort + 2 Converging Pointers | 167: 2 Converging Pointers | O(n2) |
| O(sort) |
Beating O(n2) is believed impossible (the 3SUM conjecture).
3Sum's relatives
Same sorted array, same scan as 3Sum. Only the question changes: count the triples under a target, count the triples that form a triangle, find the nearest sum, or count with repeated values.
This is 3Sum's scan with 2824's counting move. When the sum is under the target,
every index between left and right counts at once.
259. 3Sum Smaller
Brute Force
Every approach
| Approach | Time | When an interviewer wants it |
|---|---|---|
| Aux space | ||
| Brute Force | O(n3) | opening line |
| O(1) | ||
| Sort + Fix Two, Bisect the Third | O(n2 log n) | "without two pointers" |
| O(sort) | ||
| Sort + 2 Converging Pointers | O(n2) | the expected answer, and the common follow-up to 3Sum |
| O(sort) |
Sort, then fix the largest side. The other two must sum to more than it, so the same counting scan applies with the comparison flipped.
611. Valid Triangle Number
Brute Force
Every approach
| Approach | Time | When an interviewer wants it |
|---|---|---|
| Aux space | ||
| Brute Force | O(n3) | opening line |
| O(sort) | ||
| Sort + Fix Two, Bisect the Third | O(n2 log n) | "without two pointers" |
| O(sort) | ||
| Sort + Fix Largest + 2 Converging Pointers | O(n2) | the expected answer |
| O(sort) |
Move the pointers by sum against target, as in 3Sum, and update the closest sum at every step. An exact hit can return early.
16. 3Sum Closest
Sort + Fix Two, Bisect the Third
Borrowed from Binary Search ↗Every approach
| Approach | Time | When an interviewer wants it |
|---|---|---|
| Aux space | ||
| Brute Force | O(n3) | opening line |
| O(1) | ||
| Sort + Fix Two, Bisect the Third | O(n2 log n) | "without two pointers" |
| O(sort) | ||
| Sort + 2 Converging Pointers | O(n2) | the expected answer |
| O(sort) | ||
| Hash map | does not work | "why no hash version?": hashing answers exact membership, not nearest |
| - |
On a match, count runs of equal values instead of adding 1. The values only go up to 100, so counting by value also works.
923. 3Sum With Multiplicity
Brute Force
Every approach
| Approach | Time | When an interviewer wants it |
|---|---|---|
| Aux space | ||
| Brute Force | O(n3) | opening line |
| O(1) | ||
| Fix One + Counting Map | O(n2) | simplest correct answer |
| O(n) | ||
| Sort + 2 Converging Pointers | O(n2) | "with two pointers" |
| O(sort) | ||
| Count by Value | O(n + 1012) | when the small value range is the point |
| O(101) |
Every distinct quadruplet
167 inside two loops instead of one, with the same skipping of equal neighbours.
18. 4Sum
Brute Force
Every approach
| Approach | Time | When an interviewer wants it |
|---|---|---|
| Aux space | ||
| Brute Force | O(n4) | opening line |
| O(Q) | ||
| Fix Two + 1-Pass Index Map | O(n3) | when the input can't be sorted |
| O(n + Q) | ||
| Sort + Fix Three, Bisect the Fourth | O(n3 log n) | "without two pointers" |
| O(sort + Q) | ||
| Sort + Fix Two + 2 Converging Pointers | O(n3) | the expected answer |
| O(sort) | ||
| Recursive kSum | O(nk-1) | "how would you do 5Sum?" |
| O(k + sort) |
Separate arrays
4Sum II looks like a harder 4Sum but sits on a different ladder, because it asks how many tuples sum to zero. Tuples from four arrays are distinct by construction, so nothing needs deduping, and you only return a count.
Hash every pairwise sum of the first two arrays, then look up the negation of every pairwise sum of the last two: O(N2) time, O(N2) space. The map comes back because the answer is a single number again.
454. 4Sum II
Meet in the Middle (2 + 2)
Borrowed from Hash & Set ↗Every approach
| Approach | Time | When an interviewer wants it |
|---|---|---|
| Aux space | ||
| Brute Force | O(n4) | opening line |
| O(1) | ||
| Count one array (1 + 3) | O(n3) | "memory is tight" |
| O(n) | ||
| Meet in the Middle (2 + 2) | O(n2) | the expected answer |
| O(n2) | ||
| Sorted Pair Sums + 2 Converging Pointers | O(n2 log n) | "no hashing" |
| O(n2) | ||
| Generalized kSum Count | O(nk/2) | "what about 6 arrays?" |
| O(nk/2) |
Split the arrays into two halves and meet in the middle, as 454 does: O(Nk/2) time and space.
kSum Count
Given k integer arrays arrays[0], ..., arrays[k - 1], each of length n, return the number of tuples (i_0, ..., i_{k-1}) such that arrays[0][i_0] + arrays[1][i_1] + ... + arrays[k-1][i_{k-1}] == 0.
This generalizes 454. 4Sum II from four arrays to any k. The solution below is written against the 4-array signature, and kSum(arrays) is the general part.
Example 1:
Explanation: the two tuples are:
(0, 0, 0, 1):1 + (-2) + (-1) + 2 = 0(1, 1, 0, 0):2 + (-1) + (-1) + 0 = 0
Example 2:
Example 3:
Explanation: every sum is an odd count of +1 and -1, so it is odd and never 0.
Constraints:
1 <= k <= 61 <= n <= 30-228 <= arrays[i][j] <= 228- The answer fits in a 64-bit integer.
Meet in the Middle
Borrowed from Hash & Set ↗Numbers arrive one at a time
There is no array up front, so you choose which call pays: precompute the sums so find is O(1), or count the values so add is O(1).
170. Two Sum III - Data structure design
Design a data structure that accepts a stream of integers and checks if it has a pair of integers that sum up to a particular value. Implement the TwoSum class: TwoSum() initializes with an empty array, void add(int number) adds number to the data structure, and boolean find(int value) returns true if there exists any pair of numbers whose sum is equal to value, otherwise false.
["TwoSum", "add", "add", "add", "find", "find"]with[[], [1], [3], [5], [4], [7]]returns[null, null, null, null, true, false]:1 + 3 = 4, and no pair sums to7.- Constraints:
-105 <= number <= 105,-231 <= value <= 231 - 1, at most104calls in total toaddandfind.
Set of Sums
Borrowed from Hash & Set ↗Every approach
| Design | add | find | Space |
|---|---|---|---|
| Set of Sums | O(n) | O(1) | O(n + min(n(n-1)/2, R)) |
| Count Map | O(1) | O(d) | O(d) |
| Sorted List + 2 Converging Pointers | O(log n + n) | O(n) | O(n) |
Which one depends on whether add or find calls dominate.
The input is a BST
A BST is sorted input with no indices. You can't put pointers at 0 and n-1,
so each rung of the 167 ladder has to get the order back some other way.
| Approach | Aux space | Cost |
|---|---|---|
| Hash set over any traversal (Two Sum's map) | O(n + h) | ignores the BST order |
| Search the tree for each node's complement | O(2h) | O(n·h) time |
| Inorder into a list, then 2 Converging Pointers | O(n + h) | rebuilds the array that 167 started with |
| Min and max iterators | O(h) | the expected answer |
Min and max iterators run 167's two pointers on the tree itself. The min
iterator is a stack-based inorder walk: push the left spine, and after each pop
push the left spine of the popped node's right child. Each next() returns the
next-smallest value. The max iterator is its mirror (right spine, then the left
child's right spine), returning the next-largest value. Sum too low: advance
min. Sum too high: advance max. Stop when both return the same node. Each stack
holds one root-to-leaf path, so it costs O(h) instead of the list's O(n).
653. Two Sum IV - Input is a BST
DFS (Iterative, BST search per node)
The constraint matrix
| Problem | Input | Answer shape | Best time | Aux space |
|---|---|---|---|---|
| 1 Two Sumthe hub | Unsorted | One pair of indices | O(N) | O(N)the index map |
| 167 Two Sum IIfrom 1 | Sorted | One pair of indices | O(N) | O(1)the sorting is the map |
| 2824 Count Pairs Under Targetfrom 167 | Unsorted | A count of pairs | O(N log N) | O(1)beyond the sort |
| 1099 Two Sum Less Than Kfrom 167 | Unsorted | The largest sum under k | O(N log N) | O(1)beyond the sort |
| 2563 Count the Number of Fair Pairsfrom 2824 | Unsorted | A count of pairs in a range | O(N log N) | O(1)beyond the sort |
| 15 3Sumfrom 167 | Unsorted | All unique triples | O(N2) | O(1)beyond the sort |
| 259 3Sum Smallerfrom 15 | Unsorted | A count of triples | O(N2) | O(1)beyond the sort |
| 611 Valid Triangle Numberfrom 15 | Unsorted | A count of triples | O(N2) | O(1)beyond the sort |
| 16 3Sum Closestfrom 15 | Unsorted | The nearest sum | O(N2) | O(1)beyond the sort |
| 923 3Sum With Multiplicityfrom 15 | Unsorted | A count, repeats included | O(N2) | O(1)counts over a fixed value range |
| 18 4Sumfrom 15 | Unsorted | All unique quadruples | O(N3) | O(1)beyond the sort |
| 454 4Sum IIfrom 18 | Four separate arrays | A count, not the tuples | O(N2) | O(N2)the map comes back |
| kSum kSum Countfrom 454 | k separate arrays | A count | O(Nk/2) | O(Nk/2)the map comes back |
| 170 Two Sum IIIfrom 1 | A stream of adds | Yes or no, per query | O(1) addor O(1) find, not both | O(d)the count map |
| 653 Two Sum IVfrom 167 | A BST, no indices | Yes or no | O(N) | O(h)two stack iterators |
When the answer changes from one pair to every distinct tuple, early return is gone and deduping becomes the work. When it shrinks to a count over separate arrays, the map returns.