Maximmum Product of Three Numbers


A priority queue based approach would be scalable. Especially useful for when the interviewer follows up with "what if we need the max product of 100 numbers".
> https://discuss.leetcode.com/topic/94243/scalablesolutionusingpriorityqueuejava

@vinod23 Hi, To my surprise, I figured out that the time complexity of single scan is more than the time complexity of sorting one, which is O(nlogn), after I submitted the code. Can you explain the reason?

@vpb8262 Actually it depends on array size. Let say our linear algo takes 10n time and our sorting algo takes nlogn time. Now ,for sorting algo to be faster than linear one 10n > nlogn i.e. n >1024. Now if in the given test cases average size of array is less than 1024 then sorting algo will be faster.


@venkat Why use a priority queue which additional space, when sorting does the same job in O(n log n) while taking scalability into consideration?

@vinod23 Why comparing 10n and nlogn? Solution 3 takes O(n) time, shouldn't we compare n and nlogn?

int maximumProduct(int* nums, int numsSize) {
// define args
int i, j, k, sort_temp;
int maximum, maximum2;// sort nums for(i = 0; i < numsSize; i++) { for(j = i+1; j < numsSize; j++) { if(nums[j] > nums[i]) { sort_temp = nums[i]; nums[i] = nums[j]; nums[j] = sort_temp; } } } // maximum maximum = nums[0]*nums[1]*nums[2]; maximum2 = nums[0]*nums[numsSize1]*nums[numsSize2]; // return return maximum>maximum2?maximum:maximum2;
}
I tried the second solution with C, but Time Limit Exceeded.

var maximumProduct = function(nums) { var productStart = ''; var productEnd = ''; nums = nums.sort(sortNumber); productStart = nums[0] * nums[1] * nums[2] productEnd = nums[0] * nums[nums.length1] * nums[nums.length2] return productStart > productEnd ? productStart : productEnd
};
function sortNumber(a,b)
{
return b  a
}