Nkwachi's Cave

Solving the Maximum Pairwise Product Algorithm

Nkwachi Nwamaghinna's photo
Nkwachi Nwamaghinna
·

2 min read

What is the Maximum Pairwise Product? It means that we have to find the maximum product of two distinct numbers in a given array of non-negative numbers.

Problem Statement

Given a sequence of non-negative integers a0,…,an−1, find the maximum pairwise product, that is, the largest integer that can be obtained by multiplying two different elements from the sequence.

Input format:

The first line of the input contains an integer n. The next line contains n non-negative integers a0,…,an−1 (separated by spaces).

Constraints:

2≤n≤2⋅105; 0≤a0,…,an−1≤105.

Output format:

Output a single number — the maximum pairwise product.

Solution

One approach is finding the two largest numbers in the array and storing their value in two variables and then multiplying both numbers but this approach makes you run into a problem when you have an array where the largest number is repeated e.g [2,5,9,9]. When finding the second largest number you compare against the largest number to ensure they aren't the same and you'll end up with 9 and 5 giving a maximum pairwise product of 45 instead of 81.

A better approach is to store the indices of the largest number and the second-largest number, this approach eliminates the error stated above.

My solution

Here is my solution implemented in Kotlin.

fun main() {
    val scanner = Scanner(System.`in`)
    val sizeOfArray = scanner.nextInt()
    val array = mutableListOf<Int>()
    for(num in 0 until sizeOfArray){
        array.add(scanner.nextInt())
    }
    println(maxPairWiseProgram(array))
}


fun maxPairWiseProgram(array : List<Int>): Int {
    var maxIndex1 = 0
    var maxIndex2 = 0

    val arraySize = array.size

   //find index of largest number
   for(i in 1 until  arraySize) {
       if(array[maxIndex1] < array[i]){
           maxIndex1 = i
       }
   }


    //find index of second-largest number
    for(i in 1 until  arraySize) {
        if(maxIndex1 == 0) maxIndex2 = 1
        if(array[maxIndex2] < array[i] && i != maxIndex1){
            maxIndex2 = i
        }
    }

    return  array[maxIndex1] * array[maxIndex2]
}

First of I created two variables to store the indices of the largest number and second-largest number. The next step was to find the largest number which was quite straightforward. When finding the second largest number I had to check if the index of the largest number is 0 and initialize the index of the second largest number to 1 instead or else I get 0 as the index of the second-largest number which is wrong.

Conclusion:

My solution has a complexity of O(n) but it can be better as I go through the array twice and it's possible to go through the array once while keeping track of the largest number and the second-largest number simultaneously. I intend to solve the algorithm using that approach so look out for part 2 on "Solving the Maximum Pairwise Product Algorithm".

algorithmsdata structures