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.