Introduction

The task is to find the product of 3 numbers for an array such that the result is greater than the product of any 3 numbers in the same array.

---

Prompt

Given an integer array, find three numbers whose product is maximum and return the maximum product.

//Example 1:
Input: nums = [1,2,3]
Output: 6
//Explanation : Product of nums[0] * nums[1] * nums[3] i.e 1*2*3 will be 6.

//Example 2:
Input : nums = [-100,-98,-1,2,3,4]
Output : 39200
//Explanation : Product of -100 * -98 * 4 is 39200

---

Solution

For this question, there can be multiple solutions but I am mainly focusing on 2 solutions i.e. a brute force and an optimized solution.

---

Brute Force Approach

// brute force approach
const maximumProduct = (nums) => {

    let maxProduct = -Infinity

    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            let product
            for (let k = j + 1; k < nums.length; k++) {
                product = nums[k] * nums[j] * nums[i]
                maxProduct = Math.max(maxProduct, product)
            }
        }
    }
    return maxProduct
}

const nums = [-100, -98, -1, 2, 3, 4]
const result = maximumProduct(nums)
console.log(result) // 39200

The time complexity for this approach will be O(n^3) as there are 3 nested loops as the input size increases, the number of iterations grows exponentially, resulting in a slow runtime.

The space complexity will be O(1) as we are not creating any new space.

---

Optimized Approach

// optimized approach
const maximumProduct = (nums) => {

    // sorting the array in increasing order
    nums.sort((a, b) => a - b) 

    const n = nums.length; // get length of sorted array

    // find product of last 3 numbers 
    const product1 = nums[n - 1] * nums[n - 2] * nums[n - 3];
    // find product of first 2 numbers  and last number
    const product2 = nums[0] * nums[1] * nums[n - 1];
    // compare and find max between two products
    const maxProduct =  Math.max(product1, product2);

    return maxProduct
}


const nums = [-100, -98, -1, 2, 3, 4]
const result = maximumProduct(nums)
console.log(result) // 39200

The time complexity for this approach will be O(nlogn). This is because the sort method used to sort the input array has a time complexity of O(nlogn). After sorting, the function performs a constant amount of operations, which take O(1) time complexity.

The space complexity will be O(1) as we are not creating any new space.

---

Ending Note

This is one of the easiest problems present in LeetCode and will improve your coding skills.

Always try to come up with a brute-force approach first.