How I Optimized the Maximum Pairwise Product: From O(n^2) to O(n)

When starting the Data Structures and Algorithms specialization by UC San Diego on Coursera, the "Maximum Pairwise Product" problem is one of the first real tests of algorithmic efficiency. It’s a perfect example of how a "correct" solution can still be a "wrong" solution if it doesn't scale. The Problem: Given a sequence of non-negative integers, find the maximum product of two distinct numbers in the sequence. The Naive Approach : O(n^2) The most intuitive way to solve this is to use a nested loop to check every possible pair: long maxProduct = 0 ; for ( int i = 0 ; i < n ; i ++) { for ( int j = i + 1 ; j < n ; j ++) { if (( long ) arr [ i ] * arr [ j ] > maxProduct ) { maxProduct = ( long ) arr [ i ] * arr [ j ]; } } } The Flaw: This works fine for small arrays. However, if the input size is 10^5, the number of operations reaches 10^{10}, which will lead to a Time Limit Exceeded (TLE) error in most competitive programming environments. The Optimized Approach : O(n) Instead of compar