DEV Community

Redha Zidan
Redha Zidan

Posted on

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

#algorithms #programming #beginners #learning

Coding Algorithm

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];
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

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 comparing every pair, we only need the two largest numbers in the array. We can find these in a single pass (O(n)) without even sorting the array (which would be O(n log n)).

static long maxPairwiseProduct(int[] array) {
        long result = 0;
        if (array.length == 1) {
            return array[0];
        }
        long max1 = 0;
        int indexOfMax1 = 0;
        long max2 = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] > max1) {
                max1 = array[i];
                indexOfMax1 = i;
            }
        }
        for (int i = 0; i < array.length; i++) {
            if (array[i] > max2 && i != indexOfMax1) {
                max2 = array[i];
            }
        }
        result = max1 * max2;
        return result;
    }
Enter fullscreen mode Exit fullscreen mode

The Logic:

  • Find the index of the largest number.
  • Find the index of the second largest number (ensuring it's not the same index as the first).
  • Multiply them.

The "Gotcha": Integer Overflow
Even with a fast algorithm, you can fail the test cases if you don't account for the size of the result.
In many languages, a standard int is 32-bit (max value approx 2 times 10^9). If the input numbers are 2 times 10^5, their product is 4 times 10^{10}. This exceeds the capacity of an int, leading to a negative result due to overflow.
The fix is simple but vital: Use a 64-bit integer (long in Java/C# or long long in C++) for the product calculation.

Conclusion
This problem is a great reminder that software engineering isn't just about solving the logic, it's about:

  • Time Complexity: Making sure it runs fast enough for the real world.
  • Memory & Type Safety: Anticipating where the hardware limits might break your math.

What was your first "aha!" moment with Big O notation? Let me know in the comments!

Top comments (0)