# 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 ^{3})**.

### 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 ^{3}) to O(n^{2}). **Hence, making it more time-efficient. We follow the steps below to achieve this.

- Sort the array a.
- Create a HashSet of <Integer, Boolean> type.
- Store elements from 0 to highest integer in array a as key and false as value.
- Use a for loop and assign all the keys of the HashSet that are present in array a, a value true.
- Use a nested for loop to traverse the array from the rear end and get product all pair in array a.
- 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.
- 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

## Leave a Reply