You are given an array of integers, nums. Your task is to determine the maximum product that can be obtained by multiplying any three numbers from this array.
Input: nums = [1,2,3]
Output: 6
Input: nums = [1,2,3,4]
Output: 24
Input: nums = [-1,-2,-3]
Output: -6
Consider the possibility of negative numbers in the array. The product of two negative numbers and one positive number might be greater than the product of three positive numbers.
Ensure your solution is efficient and handles the maximum constraint gracefully.
function maximumProductOfThree_SortAndSelect(nums) {
nums.sort((a, b) => a - b);
const n = nums.length;
return Math.max(nums[n-1] * nums[n-2] * nums[n-3], nums[0] * nums[1] * nums[n-1]);
}
const nums1 = [1,2,3];
maximumProductOfThree_SortAndSelect(nums1); //output: 6
const nums2 = [1,2,3,4];
maximumProductOfThree_SortAndSelect(nums2); //output: 24
const nums3 = [-1,-2,-3];
maximumProductOfThree_SortAndSelect(nums3); //output: -6
function maximumProductOfThree_Heap(nums) {
class MaxHeap {
constructor() {
this.heap = [];
}
insert(val) {
this.heap.push(val);
this.heapifyUp();
}
extractMax() {
const max = this.heap[0];
this.heap[0] = this.heap.pop();
this.heapifyDown();
return max;
}
heapifyUp() {
let index = this.heap.length - 1;
while (index > 0) {
let parentIndex = Math.floor((index - 1) / 2);
if (this.heap[index] <= this.heap[parentIndex]) break;
[this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
index = parentIndex;
}
}
heapifyDown() {
let index = 0;
while (true) {
let left = 2 * index + 1;
let right = 2 * index + 2;
let largest = index;
if (left < this.heap.length && this.heap[left] > this.heap[largest]) largest = left;
if (right < this.heap.length && this.heap[right] > this.heap[largest]) largest = right;
if (largest === index) break;
[this.heap[index], this.heap[largest]] = [this.heap[largest], this.heap[index]];
index = largest;
}
}
}
const maxHeap = new MaxHeap();
for (const num of nums) {
maxHeap.insert(num);
}
const largest = [maxHeap.extractMax(), maxHeap.extractMax(), maxHeap.extractMax()];
return largest.reduce((prod, val) => prod * val, 1);
}
const nums1 = [1,2,3];
maximumProductOfThree_Heap(nums1); //output: 6
const nums2 = [1,2,3,4];
maximumProductOfThree_Heap(nums2); //output: 24
const nums3 = [-1,-2,-3];
maximumProductOfThree_Heap(nums3); //output: -6
function maximumProductOfThree_MinHeap(nums) {
class MinHeap {
constructor() {
this.heap = [];
}
insert(val) {
this.heap.push(val);
this.heapifyUp();
}
extractMin() {
const min = this.heap[0];
this.heap[0] = this.heap.pop();
this.heapifyDown();
return min;
}
heapifyUp() {
let index = this.heap.length - 1;
while (index > 0) {
let parentIndex = Math.floor((index - 1) / 2);
if (this.heap[index] >= this.heap[parentIndex]) break;
[this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
index = parentIndex;
}
}
heapifyDown() {
let index = 0;
while (true) {
let left = 2 * index + 1;
let right = 2 * index + 2;
let smallest = index;
if (left < this.heap.length && this.heap[left] < this.heap[smallest]) smallest = left;
if (right < this.heap.length && this.heap[right] < this.heap[smallest]) smallest = right;
if (smallest === index) break;
[this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
index = smallest;
}
}
}
const minHeap = new MinHeap();
for (const num of nums) {
minHeap.insert(num);
if (minHeap.heap.length > 3) {
minHeap.extractMin();
}
}
const largestThree = minHeap.heap;
return largestThree[0] * largestThree[1] * largestThree[2];
}
const nums1 = [1,2,3];
maximumProductOfThree_MinHeap(nums1); //output: 6
const nums2 = [1,2,3,4];
maximumProductOfThree_MinHeap(nums2); //output: 24
const nums3 = [-1,-2,-3];
maximumProductOfThree_MinHeap(nums3); //output: -6
function maximumProductOfThree_BruteForce(nums) {
let maxProduct = -Infinity;
for (let i = 0; i < nums.length - 2; i++) {
for (let j = i + 1; j < nums.length - 1; j++) {
for (let k = j + 1; k < nums.length; k++) {
const product = nums[i] * nums[j] * nums[k];
maxProduct = Math.max(maxProduct, product);
}
}
}
return maxProduct;
}
const nums1 = [1,2,3];
maximumProductOfThree_BruteForce(nums1); //output: 6
const nums2 = [1,2,3,4];
maximumProductOfThree_BruteForce(nums2); //output: 24
const nums3 = [-1,-2,-3];
maximumProductOfThree_BruteForce(nums3); //output: -6
function maximumProductOfThree_LargestTwoSmallest(nums) {
let max1 = -Infinity, max2 = -Infinity, max3 = -Infinity;
let min1 = Infinity, min2 = Infinity;
for (const num of nums) {
if (num > max1) {
[max3, max2, max1] = [max2, max1, num];
} else if (num > max2) {
[max3, max2] = [max2, num];
} else if (num > max3) {
max3 = num;
}
if (num < min1) {
[min2, min1] = [min1, num];
} else if (num < min2) {
min2 = num;
}
}
return Math.max(max1 * max2 * max3, max1 * min1 * min2);
}
const nums1 = [1,2,3];
maximumProductOfThree_LargestTwoSmallest(nums1); //output: 6
const nums2 = [1,2,3,4];
maximumProductOfThree_LargestTwoSmallest(nums2); //output: 24
const nums3 = [-1,-2,-3];
maximumProductOfThree_LargestTwoSmallest(nums3); //output: -6
function maximumProductOfThree_SortingOptimized(nums) {
nums.sort((a, b) => a - b);
const n = nums.length;
return Math.max(
nums[n-1] * nums[n-2] * nums[n-3],
nums[0] * nums[1] * nums[n-1]
);
}
const nums1 = [1,2,3];
maximumProductOfThree_SortingOptimized(nums1); //output: 6
const nums2 = [1,2,3,4];
maximumProductOfThree_SortingOptimized(nums2); //output: 24
const nums3 = [-1,-2,-3];
maximumProductOfThree_SortingOptimized(nums3); //output: -6
function maximumProductOfThree_Greedy(nums) {
let [max1, max2, max3] = [-Infinity, -Infinity, -Infinity];
let [min1, min2] = [Infinity, Infinity];
for (const num of nums) {
if (num > max1) {
[max3, max2, max1] = [max2, max1, num];
} else if (num > max2) {
[max3, max2] = [max2, num];
} else if (num > max3) {
max3 = num;
}
if (num < min1) {
[min2, min1] = [min1, num];
} else if (num < min2) {
min2 = num;
}
}
return Math.max(max1 * max2 * max3, max1 * min1 * min2);
}
const nums1 = [1,2,3];
maximumProductOfThree_Greedy(nums1); //output: 6
const nums2 = [1,2,3,4];
maximumProductOfThree_Greedy(nums2); //output: 24
const nums3 = [-1,-2,-3];
maximumProductOfThree_Greedy(nums3); //output: -6
function maximumProductOfThree_Set(nums) {
const topThree = Array.from(new Set(nums)).sort((a, b) => a - b).slice(-3);
const bottomTwo = Array.from(new Set(nums)).sort((a, b) => a - b).slice(0, 2);
if (topThree.length < 3) throw new Error("Array must have at least three unique elements");
const maxProduct = Math.max(
topThree.reduce((prod, val) => prod * val, 1),
topThree[0] * bottomTwo[0] * bottomTwo[1]
);
return maxProduct;
}
const nums1 = [1,2,3];
maximumProductOfThree_Set(nums1); //output: 6
const nums2 = [1,2,3,4];
maximumProductOfThree_Set(nums2); //output: 24
const nums3 = [-1,-2,-3];
maximumProductOfThree_Set(nums3); //output: -6