CC-4 : Find maximum product of 2 integers in an Array.

Description:

Given an array of integers as input array, find the maximum product of 2 integers within the array.

Test cases and expected outputs:

Input Parameters	Expected outputs
int[] nums= {3,3,3,4,7,9,3,4,10,15,11,1,1,7, -9, -3, -4, -23};	Max Product: 207 Num1: -23 Num2: -9

Pseudocode:

Initialize a PriorityQueue instance maxHeap to be used as max Heap.

Initialize a PriorityQueue instance minHeap to be used as min Heap.

We get array of integers nums as input parameter.

Iterate though nums from index 0 to index nums.length-1:

Add nums[idx]to maxHeap.

Add nums[idx]to minHeap.

Extract 2 top numbers from maxHeap and store their product in variable maxProd.

Extract 2 top numbers from minHeap and store their product in variable minProd.

If maxProd > minProd, return maxProd from method.

Else if maxProd < minProd, return minProd from method.

Code:

public class HeapFindMaxProductOf2Int {
	
private PriorityQueue<Integer> maxHeap=new PriorityQueue<Integer>(Collections.reverseOrder());	
private PriorityQueue<Integer> minHeap=new PriorityQueue<Integer>();
 
public int[] findMaxProductOf2Int(int[] arr) {
	for (int idx=0; idx < arr.length; idx++) {
		maxHeap.add(arr[idx]);
		minHeap.add(arr[idx]);
	}
	int maxInt1=maxHeap.remove();
	int maxInt2=maxHeap.remove();
	int minInt1=minHeap.remove();
	int minInt2=minHeap.remove();
	
	int maxProd=maxInt1 * maxInt2;
	int minProd=minInt1 * minInt2;
	
	if  (maxProd >= minProd) {
		int[] retVal= {maxProd,maxInt1,maxInt2};
		return retVal;
	} else {
		int[] retVal= {minProd,minInt1,minInt2};
		return retVal;
	}
	
}
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

import java.util.Collections;
import java.util.PriorityQueue;

public class HeapFindMaxProductOf2Int {
	
private PriorityQueue<Integer> maxHeap=new PriorityQueue<Integer>(Collections.reverseOrder());	
private PriorityQueue<Integer> minHeap=new PriorityQueue<Integer>();
 
public int[] findMaxProductOf2Int(int[] arr) {
	for (int idx=0; idx < arr.length; idx++) {
		maxHeap.add(arr[idx]);
		minHeap.add(arr[idx]);
	}
	int maxInt1=maxHeap.remove();
	int maxInt2=maxHeap.remove();
	int minInt1=minHeap.remove();
	int minInt2=minHeap.remove();
	
	int maxProd=maxInt1 * maxInt2;
	int minProd=minInt1 * minInt2;
	
	if  (maxProd >= minProd) {
		int[] retVal= {maxProd,maxInt1,maxInt2};
		return retVal;
	} else {
		int[] retVal= {minProd,minInt1,minInt2};
		return retVal;
	}
	
}

public static void printArraySummary(int[] intArray, String label) throws Exception {
   	// Case 1: The input Array is null !!
	if (intArray == null) { System.out.println("\n\n Input Array was null !! \n"); return; }
	// Case 2: Print input Array by index (first to last)
	System.out.println();
	System.out.println("************************************************************************");
	System.out.print(label+" : ");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex < intArray.length; arrayIndex++) {
			System.out.print(intArray[arrayIndex]);
			if (arrayIndex < intArray.length-1) {System.out.print(",");}
	} 
	System.out.println();
	System.out.println(" ************************************************************************");
		System.out.println();
		Thread.sleep(2000);
		return;
}

public static void main(String[] args) {
	/**********************
	 Test cases given below
	 *********************/
	int[] retVal;
	try {
	HeapFindMaxProductOf2Int hp=new HeapFindMaxProductOf2Int();
	int[] nums= {3,3,3,4,7,9,3,4,10,15,11,1,1,7, -9, -3, -4, -23};
	printArraySummary(nums, "Nums");
	retVal=hp.findMaxProductOf2Int(nums);
	System.out.println("Max Product: "+ retVal[0]);
	System.out.println("Num1: "+ retVal[1]);
	System.out.println("Num2: "+ retVal[2]);
		
	}catch (Exception exception) {
	System.out.print("Exception: "+ exception);
	exception.printStackTrace();
	}
		
}


}