JuniorCodeCommonNot answered yet
Return the two largest numbers in an array in one pass
Return the two largest values in an array of integers in a single linear pass. Handle negative numbers and duplicates correctly.
Requirements:
- O(n) time, O(1) space — do not sort.
- Decide what to do for an array of fewer than two elements (e.g. report it).
std::pair<int,int> twoLargest(const std::vector<int>& a) {
// your code here
}Write the implementation.
Keep two variables, max1 and max2, both initialised to the smallest possible value (not 0). For each element: if it exceeds max1, shift max1 into max2 and update max1; else if it exceeds max2, update max2. The crucial else if keeps the old max from being lost. One pass, O(n).
- ✗Omitting the
else if (x > max2)branch, so the second-largest is overwritten by the largest - ✗Initialising the maxima to 0, which breaks for all-negative arrays
- ✗Not handling an array of fewer than two elements
- →Why does initialising to 0 fail for an all-negative array?
- →How would you generalise this to the K largest elements?
Contents
Task
Return the two largest values in one O(n) pass, no sorting, correct for negatives and duplicates.
Solution
std::pair<int,int> twoLargest(const std::vector<int>& a) {
if (a.size() < 2) throw std::invalid_argument("need at least 2 elements");
int max1 = INT_MIN, max2 = INT_MIN;
for (int x : a) {
if (x > max1) { max2 = max1; max1 = x; } // new max, old one -> second
else if (x > max2) { max2 = x; } // the required branch
}
return {max1, max2};
}Key points
else if (x > max2)rescues the old max — without it the second-largest is lost.- Initialise to
INT_MIN, not 0 — otherwise an all-negative array breaks. - One pass, O(n) time, O(1) space.
Contents
