Largest product of two numbers in a list
Given a list of integers (which may include negatives), return the largest product obtainable by multiplying two distinct elements. Aim for O(n) time, O(1) space.
Example: [-10, -9, 1, 2] → 90 (from -10 * -9).
def max_pair_product(nums: list[int]) -> int:
# your code hereWrite the implementation.
The answer is max(top1 * top2, bottom1 * bottom2) — the two largest values OR the two smallest. The second candidate matters because two large-magnitude negatives multiply to a large positive. Find the top two and bottom two in one O(n) pass (or sorted for O(n log n)).
- ✗Multiplying only the two largest, missing two negatives
- ✗Pairing the max with the min instead of two extremes
- ✗Dropping signs by taking absolute values
- →On which input does the two-largest-only approach fail?
- →How would you do it in one pass without sorting?
The maximum product is either the two largest values or the two smallest (two big negatives multiply to a big positive), so compare both candidates.
def max_pair_product(nums: list[int]) -> int:
s = sorted(nums) # O(n log n); a one-pass O(n) scan also works
return max(s[-1] * s[-2], s[0] * s[1])For [-10, -9, 1, 2]: two largest give 1 * 2 = 2, but two smallest give -10 * -9 = 90, so the answer is 90. Checking only the two largest would wrongly return 2. Tracking the top-two and bottom-two values in a single linear scan achieves O(n) time, O(1) space.
