Maximmum Product of Three Numbers


  • 0

    Click here to see the full article post


  • 0
    V

    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/scalable-solution-using-priority-queue-java


  • 0
    V

    @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?


  • 0

    @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.


  • 0
    V

    @vinod23 Thanks for your reply. It also depends upon the size of array.


  • 0
    S

    What if the array has only 2 elements or 1 element? I believe an error check needs to be there to validate that.


  • 0
    S

    @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?


  • 0
    G

    Why Approach #3 works? Could you please provide reasons?


  • 0
    E

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


  • 0
    S

    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[numsSize-1]*nums[numsSize-2];
    
    // return
    return maximum>maximum2?maximum:maximum2;
    

    }

    I tried the second solution with C, but Time Limit Exceeded.


  • 0
    E

    var maximumProduct = function(nums) {
    var n=nums.length;
    nums.sort(function (a,b) {return b-a});
    var maximum=nums[0]*nums[1]*nums[2];
    s=Math.max(maximum,nums[0]*nums[n-1]*nums[n-2]);
    return s
    };


  • 0
    var maximumProduct = function(nums) {
        var productStart = '';
        var productEnd = '';
        nums = nums.sort(sortNumber);
        productStart = nums[0] * nums[1] * nums[2]
        productEnd = nums[0] * nums[nums.length-1] * nums[nums.length-2]
        return productStart > productEnd ? productStart : productEnd
    

    };
    function sortNumber(a,b)
    {
    return b - a
    }


  • 0
    C

    class Solution {
    public int maximumProduct(int[] nums) {
    Arrays.sort(nums);
    int n = nums.length;
    int s = nums[n-1] * nums[n-2] * nums[n-3]; // 全是正数
    s = Math.max(s, nums[n-1] * nums[1] * nums[0]); // 前两个是负数
    return s;
    }
    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.