Java program to find a pair with the greatest product in an array

In this tutorial, we will write a Java program to find a pair with the greatest product in an array using a Brute Force as well as a Time-Efficient Approach.

Brute Force Approach

First, we can simply iterate over the list using two for loops to find out the product of all the pairs. Then we use another loop to check if the product if greater than the previous max and if it exists in the array as well. If all these conditions are true we assign the new product to max and add the elements that generate this product to the out result array. This is a Naive Approach and will give a worst-case complexity of O(n³).

Java Implementation

The following code shows the implementation of the above steps in Java.

import java.io.*; 
  
class greatestProduct
{ 
  
static int[] greatestProductPair(int elements[]) 
{ 
    int n = elements.length;
    int i=0, j=0, k=0;
    // this array has elem1, elem2, product of elem1 & elem2 
    // at 0,1,2 indices respectively
    int result[] = {-1,-1,-1}; 
    
    for (i = 0; i < n ; i++) {
        for (j = 0; j < n-1; j++) {
            for (k = j+1 ; k < n ; k++) {
                if (elements[j] * elements[k] == elements[i])
                { 
                    result[0] = elements[j]; // elem1
                    result[1] = elements[k]; // elem2
                    // max product
                    result[2]  = Math.max(result[2],elements[i]);
                }
                
            }
        }
    }
    
    return result; 
} 
  
    public static void main (String args[]) 
    { 
        int elements[] = {2, 3, 4, 7, 9}; 
        int result[] = greatestProductPair(elements);
        
        if (result[0] == -1)
            System.out.println("No greatest product");
         
        else
            System.out.println("Product of "+result[0]+" * "
                            + result[1]+ " = " + result[2] + 
                            " is the greatest in the array"); 
    } 
}

INPUT  
elements: {3, 18, 6, 9, 2, 24, 4}
OUTPUT
result = {6, 4, 24} 
Product of 6 * 4 = 24 is the greatest in the array

INPUT
elements: {2, 3, 4, 7, 9} 
OUTPUT
result = {-1, -1, -1}
No greatest product

Time Efficient Approach

Here we try to reduce the complexity.
Upon a little pondering, we conclude that we can reduce the complexity by eliminating the third loop by using a HashSet in Java

HashSet in Java is a special type of Map data structure that started a key-value pair of unique key elements.

The complexity of fetching elements from HashSet is O(1). Therefore, we can reduce the time complexity from O(n³) to O(n²). Hence, making it more time-efficient. We follow the steps below to achieve this.

1. Sort the array a.
2. Create a HashSet of <Integer, Boolean> type.
3. Store elements from 0 to highest integer in array a as key and false as value.
4. Use a for loop and assign all the keys of the HashSet that are present in array a, a value true.
5.  Use a nested for loop to traverse the array from the rear end and get product all pair in array a.
6. If the product is greater than the existing max product and it has value true in  HashSet. Then make this max and note the elements generating in the product.
7. Return the array containing max product and the elements generating it.

Java Implementation

The following code shows the implementation of the above steps in Java.

import java.util.*;

class Main 
{ 
  public static int[] greatestProductPair(int a[]) 
  { 
    int n = a.length, result[] ={-1,-1,-1}, product;
  
    // sort the array
    Arrays.sort(a); 
    
    // Store elements in hash array 
    Map<Integer, Boolean> elem = new HashMap<>();
    for (int i =1; i < a[n-1]+1; i++)
        elem.put(i,false);
    
    for (int i = 0; i < n; i++) 
    { 
      if (elem.containsKey(a[i])) 
      { 
        elem.put(a[i], true); 
      } 
    } 

     //traverse from rear end to get max product 
    for (int i=n-1; i>0; i--) 
    {  
      for (int j = i-1; j>=0; j--) 
      { 
          product = a[i] * a[j];
        if (elem.get(product) != null && elem.get(product) == true) 
          { 
            if (result[2] < product)
            {
              result[0] = a[i];
              result[1] = a[j];
              result[2] = product;
              
            }
        }
      }
    }
    return result;
  } 

  public static void main (String args[]) 
  { 
      int elements[] = {2, 3, 4, 7, 9, 6, 24}; 
      int result[] = greatestProductPair(elements); 
      if (result[0] == -1) 
          System.out.println("No greatest product"); 
      else 
          System.out.println("Product of "+result[0]+" * "+result[1]
           +" = "+result[2]+" is the greatest in the array"); 
          
   }
}

INPUT 
elements: {1, 7, 12, 3, 4, 2, 6, 8} 
OUTPUT
result = {1, 12, 12} 
Product of 1 * 12 = 12 is the greatest in the array 

INPUT
elements: {3, 4, 2, 6, 8}
OUTPUT
result = {4, 2, 8} 
Product of 4 * 2 = 8 is the greatest in the array

• You may also like:
  Find the closest distance between a pair of a point among given n points in Java
  Pair with a given sum in an array using HashSet in Java
  How to find Maximum Pairwise Product in Java using Naive approach