JuniorCodeCommonNot answered yet
Minimum product of any pair of array elements
Given a sequence of integers, find the minimum possible product of any pair of two distinct elements (not necessarily adjacent).
Requirements:
a positive can be the minimum.
- O(n) time, O(1) space — no sorting, no nested loops.
- Account for negatives: two negatives multiply to a positive; a negative times
long long minPairProduct(const std::vector<int>& a) {
// your code here
}Write the implementation.
Track the two smallest and two largest values in one pass. The minimum product is the smaller of min1*min2 (both small/negative) and max1*max2 (two large negatives give a small product), but the overall minimum is min1 * max1 when signs are mixed — compare all relevant candidates. O(n) time, O(1) space; watch for overflow with long long.
- ✗Considering only the two smallest, missing the two-large-negatives case
- ✗Overflowing
intwhen multiplying two large-magnitude values - ✗Sorting (O(n log n)) when an O(n) tracking pass is expected
- →Why can two large negative numbers never be the minimum product?
- →How does the answer change for the maximum product instead?
Contents
Task
Find the minimum product of a pair in O(n), accounting for negatives and overflow.
Solution
long long minPairProduct(const std::vector<int>& a) {
long long min1 = LLONG_MAX, min2 = LLONG_MAX;
long long max1 = LLONG_MIN, max2 = LLONG_MIN;
for (long long x : a) {
if (x < min1) { min2 = min1; min1 = x; } else if (x < min2) min2 = x;
if (x > max1) { max2 = max1; max1 = x; } else if (x > max2) max2 = x;
}
// candidates: two smallest, two largest, extremes
return std::min({min1 * min2, max1 * max2, min1 * max1});
}Key points
- The minimum is one of three candidates:
min1*min2,max1*max2,min1*max1. long longguards against overflow when multiplying large values.- One O(n) pass beats the O(n²) double loop or O(n log n) sort.
Contents
