Given an array of integers, find maximum product of two integers in an array.

Given an array of positive and negative numbers, we have to find the maximum product of two integers in an array. 

For example -> 1,2,3,4,5,6 The maximum product of two integer = 30. 

Similarly for given input ->  5,3,2,-1,-6,-5 The maximum product of two integer = 30.

Let us discuss various approach to solve above problem.

Brute Force Method

  1. Take Max Value = Integer.MIN
  2. We can traverse the array and find multiplication of one integer with another.
  3. Max value will be compared with calculated value in step 2. If Max Value < calculated value, then Max Value = calculated value
  4. The final result will be  = Max Value.

The time complexity of above approach is O(n2) and space complexity = O(1)

Sorting Approach

  1. We can sort the given array using Merge sort.
  2. Find the product of first two numbers and last two numbers and return the maximum of both.

The time complexity of above approach is O(nlogn) and space complexity is O(1).

Using Max and second max element/Max and second max neagtive number

  1. We can traverse the array once and find max element, second max element.
  2. Similarly, we can find first max negative and second max negative number.

Code Snippet

We have to handle boundary conditions which are most important aspect of this question.

  1. If elements are less than 2.
  2. If numbers of element are = 2.

Code

public class MaxProductPair {

	public static void main(String[] args) {
		//input
		int[] inputArr = { -1, 2, 4, 9 };
		//processing+output
		findMaxProduct(inputArr);
	}

	/** This method is used to find max product pair.
	 * @param inputArr
	 */
	public static void findMaxProduct(int inputArr[]) {
		int arraySize = inputArr.length;
		if (arraySize < 2) {
			System.out
					.println("Please provide valid input. Elements in input array < 2");
			return;
		}
		if (arraySize == 2) {
			System.out.println("(" + inputArr[0] + "," + inputArr[1] + ")");
			return;
		}

		int firstMaxPositive = Integer.MIN_VALUE, secondMaxPositive = Integer.MIN_VALUE;
		int firstMinNegative = Integer.MIN_VALUE, secondMinNegative = Integer.MIN_VALUE;

		// Code to identify max's and min's
		for (int count = 0; count < arraySize; count++) {
			if (inputArr[count] > firstMaxPositive) {
				secondMaxPositive = firstMaxPositive;
				firstMaxPositive = inputArr[count];
			} else if (inputArr[count] > secondMaxPositive) {
				secondMaxPositive = inputArr[count];
			}

			if (inputArr[count] < 0
					&& Math.abs(inputArr[count]) > Math.abs(firstMinNegative)) {
				secondMinNegative = firstMinNegative;
				firstMinNegative = inputArr[count];
			} else if (inputArr[count] < 0
					&& Math.abs(inputArr[count]) > Math.abs(secondMinNegative)) {
				secondMinNegative = inputArr[count];
			}
		}

		// output code
		if (firstMinNegative == Integer.MIN_VALUE
				&& secondMinNegative == Integer.MIN_VALUE) {
			System.out.println("(" + firstMaxPositive + "," + secondMaxPositive
					+ ")");
		} else if (firstMaxPositive == Integer.MIN_VALUE
				&& secondMaxPositive == Integer.MIN_VALUE) {
			System.out.println("(" + firstMinNegative + "," + secondMinNegative
					+ ")");
		} else if (firstMaxPositive * secondMaxPositive > firstMinNegative
				* secondMinNegative) {
			System.out.println("(" + firstMaxPositive + "," + secondMaxPositive
					+ ")");
		} else {
			System.out.println("(" + firstMinNegative + "," + secondMinNegative
					+ ")");
		}
	}
}

Output

(9,4)

In this article we learnt how to find maximum product of two integers in an array.

Author
Author: Amit Gupta
Published On: 15/04/2017
Last revised On: 27/04/2017
View all articles by Amit Gupta

Share this post

Comments

Comments
comments powered by Disqus

Navigation

Social Media