MaxProductOfThree - Codility - Solution

Java solution to Codility MaxProductOfThree problem (Lesson 6 – Sorting) which scored 100%. The problem is to find the maximum product of 3 numbers in a given sequence of numbers. The strategy is to sort list of integers and then find largest product by checking the 4 combinations of products.

The largest 3 elements product will be one of these 4 values, assuming we have an ordered list:

first 3 elements (highest values)
last 3 elements (lowest values – can have 2 large negative values that create a positive and then multipled by a positive)
first element and last 2 elements
first 2 elements and last element

First, add all the array elements into a list, order the list and then find the max of the above 4 values. It has to be a java.util.List and not a java.util.Set because duplicate elements ARE allowed.

[cc lang="java" escaped="true"]
package com.codility.lesson06.sorting;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class MaxProductOfThree {
	public int solution(int[] A) {
		List aList = new ArrayList();
		for(int i=0; i<A.length; i++) {
			aList.add(A[i]);
		}
		Collections.sort(aList);
		
		int product1, product2, product3, product4 = 0;

		product1 = aList.get(0) * aList.get(1) * aList.get(2); //first 3 elements
		product2 = aList.get(aList.size()-3) * aList.get(aList.size()-2) * aList.get(aList.size()-1); //last 3 elements
		product3 = aList.get(0) * aList.get(1) * aList.get(aList.size()-1); //first 2 and last element
		product4 = aList.get(0) * aList.get(aList.size()-2) * aList.get(aList.size()-1); //first and last 2 elements

		int max1 = Math.max(product1, product2);
		int max2 = Math.max(product3, product4);
		
		return Math.max(max1, max2);
	}
}
[/cc]

TestNG test cases for this problem which all passed:

[cc lang="java" escaped="true"]
package test.com.codility.lesson06.sorting;

import org.testng.Assert;
import org.testng.annotations.BeforeTest;
import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;

import com.codility.lesson06.sorting.MaxProductOfThree;

public class MaxProductOfThreeTests {
	private MaxProductOfThree solution;
	
	@BeforeTest
	public void setUp() {
		solution = new MaxProductOfThree();
	}

	@DataProvider(name = "test1")
	public Object [][] createData1() {
		return new Object [][] {
			new Object [] {  new int [] { -3, 1, 2, -2, 5, 6  }, 60 }, //2 * 5 * 60
			new Object [] {  new int [] { -3, 1, -100, 2, -2, 5, 6  }, 1800 }, //-100 * -3 * 6
			new Object [] {  new int [] { -3, 1, -100}, 300},
			new Object [] {  new int [] { -3, 1, 0, -100}, 300}, //-100 * -3 * 1
			new Object [] {  new int [] { -3, 1, 2, 0, -100}, 600},  //-100 * -3 * 2
			new Object [] {  new int [] { 10, 10, 10 }, 1000 },
		};
	}

	@Test(dataProvider = "test1")
	public void verifySolution(int[] pA, int pExpected) {		
		Assert.assertEquals(solution.solution(pA), pExpected);
	}	
}
[/cc]

MaxProductOfThree – Codility – Solution