Java program to find the highest product of 3 elements in an array

This blog post is about java program to find the highest product of 3 elements in an array.

Introduction:

When this question is asked, the usual solution which comes to our mind will be multiplying each element with other elements and finding the maximum product out of those, which is the brute force solution. The function for brute force  approach is as follows:

  /*
  * Method to return the highest product of three elements.
  * return type: Integer
  * input: int arr[]
  */
 public static Integer returnHighestProduct(int arr[]) 
 {
  if((arr==null)||(arr.length<3))
  {
   return null;
  }
  
  else
  {
   int product = Integer.MIN_VALUE;
   for(int i=0;i<arr.length;i++)
   {
    for(int j=i+1;j<arr.length;j++)
    {
     for(int k=j+1;k<arr.length;k++)
     {
    int max_product = arr[i]*arr[j]*arr[k];
      if(max_product>=product)
      {
      product = max_product;
      }
     }
    }
   }
   return product;
  }
 }

But the time complexity in the above approach is O(n^3). We can simplify this program to a much better logic, which can be done in O(n) time complexity. The approach is as follows:

Solution:

• Initialize 3 variables max1, max2, max3 as first element of array or Integer.MIN_VALUE. These 3 variables represent the highest 3 elements in the array.
• Initialize 2 variables min1, min2 as first element of array or Integer.MAX_VALUE. These 2 variables represent the lowest 2 elements int the array.
• Find the product of max1, max2, max3 and max1, min1, min2. The highest product out of these two corresponds to the highest product of 3 elements in the array.

Java Program:

The java program for the solution is as follows:

package Programs;
/*
 * Java program to return maximum product of 3 elements in an array
 * Return null if array is null, empty or contains less than 3 elements
 * 
 * Solution: Find the 3 highest elements and 2 lowest elements in the array. Maximum product of 3 elements in the array will be larger value of product of 3 highest elements 
 * or product of 2 lowest element and the highest element
 * 
 * Time Complexity: O(n)
 */
public class MaximumProductOfThreeElements {
 
 public static void main(String[] args) {
int arr[] = new int[]{2,-4,5,-6,9,7,-4,-8,7}; 
System.out.println(returnHighestProduct(arr));//Max product = 9*7*7
  
int arr1[] = new int[]{2,4};
System.out.println(returnHighestProduct(arr1));//Max product = returns null
  
int arr2[] = new int[]{1,-1,1,3,-2,3,2,-2,3};
System.out.println(returnHighestProduct(arr2));//Max product = 3*3*3
 }
 
 /*
  * Method to return the highest product of three elements.
  * return type: Integer
  * input: int arr[]
  */
 public static Integer returnHighestProduct(int arr[]) 
 {
  if((arr==null)||(arr.length<3))
  {
   return null;
  }
  
  else
  {
   int max[] =findThreeMax(arr);
   int max1 = max[0];
   int max2 = max[1];
   int max3 = max[2];
   
   int min[] = findTwoMin(arr);
   int min1 = min[0];
   int min2 = min[1];
   
return (max1*max2*max3)>(max1*min1*min2)?(max1*max2*max3):(max1*min1*min2);
  }
 }
 
 /*
  * Method to return the highest three elements in the array
  * return type: int arr[]
  * input: int arr[]
  */
 public static int[] findThreeMax(int arr[])
 {
  int max1, max2,max3;
  max1=max2=max3= arr[0];
  
  for(int i=1;i<arr.length;i++)
  {
   if(arr[i]>=max1)
   {
    max3 = max2;
    max2 = max1;
    max1 = arr[i];
  
   }
   else if((arr[i]>=max2)&&(arr[i]<max1))
   {
    max3 = max2;
    max2 = arr[i];
   }
   
   else if((arr[i]>=max3)&&(arr[i]<max2))
   {
    max3 = max2;
   }
  }
  
  return new int[]{max1,max2,max3};
 }
 
 /*
  * Method to return the lowest two elements in the array
  * return type: int arr[]
  * input: int arr[]
  */
 public static int[] findTwoMin(int arr[])
 {
  int min1, min2;
  min1=min2=arr[0];
  
  for(int i=1;i<arr.length;i++)
  {
   if(arr[i]<=min1)
   {
    min2 = min1;
    min1 = arr[i];
  
   }
   else if((arr[i]<=min2)&&(arr[i]>min1))
   {
    min2 = arr[i];
   }
   
  }
  
  return new int[]{min1,min2};
  
 }
}

Output:

The output of the java program is as follows:

441
null
27

When the array is null or the number of elements in the array is less than 3, the function will return "null".

Other important posts in the blog:

1. Java program to check if an array is bitonic
2. Deploying GWT application on Tomcat server
3. Easy way to remove duplicates and order a list