Code Corner: Max of 3


Problem

Given an n-length Array of integers ranging from -1000 to 1000 find the largest product of three numbers in A that you can get.

Source

Example

[-3,2,6,4,8] => 192

My Solution

There are three basic scenarios that can produce the largest product:

  • The largest three positive numbers
  • The largest positive number and the smallest two negative numbers
  • The largest three negative numbers

The first task is to sort the array, that means that the largest numbers are at the right and the smallest area on the left.

a b c x y z
List

Something like this, with a, b and c being the smallest values and x, y, and z being the largest values.

The first scenario happens when x*y is greater than a*b. Consequently, the second scenario only occurs when a*b is greater than x*y. We will always use z in these two scenarios because it is the largest positive number and two negatives will always give a positive.

The third scenario only occurs when z is less than 0. In this case, we now want the smallest absolute value which happens to be the largest number.

Examples

Scenario 1
[-4, -5, 1, 2, 7, 9, 10]  x * y = 7 * 9 = 63 which is greater than a * b = -5 * -4 = 20
Scenario 2
[-9, -8, -7, 1, 2, 3] x * y = 2 which is less than a * b = 72
Scenario 3
[-5, -4, -3, -2, -1] z is negative, 

This leads to the following code

function solution(A) {
    A.sort((a,b) => a-b)
    const n = A.length
    const positiveProduct = A[n-2] * A[n-3]
    const negativeProduct = A[0] * A[1]

    if (positiveProduct > negativeProduct || A[n -1] < 0){
        return A[n-1] * positiveProduct
    }
    return A[n-1] * negativeProduct
}
Code language: JavaScript (javascript)

Notes:

  • You shouldn’t do operations on A because that mutates the A outside the function. So here normally we’d have created a copy const aCopy = [...A];
  • The positiveProduct and negativeProduct could be named better.

And that’s that.


Leave a Reply

Your email address will not be published. Required fields are marked *