Java O(1) space O(n) time solution beat 100%


  • 32

    Simply find out the three largest numbers and the two smallest numbers using one pass.

        public int maximumProduct(int[] nums) {
            int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE, min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
            for (int n : nums) {
                if (n > max1) {
                    max3 = max2;
                    max2 = max1;
                    max1 = n;
                } else if (n > max2) {
                    max3 = max2;
                    max2 = n;
                } else if (n > max3) {
                    max3 = n;
                }
    
                if (n < min1) {
                    min2 = min1;
                    min1 = n;
                } else if (n < min2) {
                    min2 = n;
                }
            }
            return Math.max(max1*max2*max3, max1*min1*min2);
        }
    

  • 0
    L

    @dreamchase
    I use your thought and change the code that make it clear.

    class Solution {
    public:
        int maximumProduct(vector<int>& nums) {
            int N = nums.size();
            if(N < 3) {
                return 0;
            }
            if(N == 3) {
                return nums[0] * nums[1] * nums[2];
            }
            sort(nums.begin(), nums.end());
            if(nums[0] >= 0 || nums.back() < 0) {
                return nums[N-1] * nums[N-2] * nums[N-3];
            } else if(nums.back() == 0) {
                N = N - 1;
                return nums[N-1] * nums[N-2] * nums[N-3];
            } else {
                return max(nums[0] * nums[1] * nums.back(), nums[N-1] * nums[N-2] * nums[N-3]);
            }
        }
    };
    

  • 8

    @liuguiyangnwpu
    This is O(nlogn) complexity rather than O(n) since you used sorting... So hard to say this is concise... If you use sort it can be just two lines:

        public int maximumProduct(int[] nums) {
            Arrays.sort(nums);
            int n = nums.length;
            return Math.max(nums[n-1]*nums[n-2]*nums[n-3], nums[n-1]*nums[0]*nums[1]);
        }
    

  • 0
    S

    @dreamchase Clean and elegant solution, thanks!


  • 0

    Great solution, thanks for sharing.


  • 0
    B

    @dreamchase I have a quick question:
    Why have you initialized min2 to Integer.MIN_VALUE? In my opinion, it should be initialized to Integer.MAX_VALUE.


  • 1

    @BatCoder You are definitely right, it was a typo and I've corrected it!


  • 0
    B

    @dreamchase Thank you!


  • 0
    L

    @dreamchase how do you get to this solution? Thank you!


  • 3

    @linxingquan Just think about three cases:
    all positive - product of last three
    one negative - product of last three
    two or more negative - either product of first two and last or product of last three


  • 0
    L

    Very smart solution


  • 0
    V

    @dreamchase Hi, I have followed your code in first case. Also, I also used the sorting one in second case. To my surprise, I figure out that the time complexity of your code is more than the time complexity of sorting one, which is O(nlogn). Can you help me to understand the concept?


  • 0
    N

    @dreamchase Why do you have to do this Math.max(max1max2max3, max1min1min2). The question is find three numbers whose product is maximum so can't we just do
    int maxVal = max1max2max3.


  • 0
    B

    @nitishleet No, you cannot. Because out of the three, if two numbers are negative, then their product (along with the third one) can be greater than that of three positive numbers. Remember that product of two negative numbers is positive. Hope this is useful.


  • 0
    V

    @nitishleet There are some negative number given in input. According to law of mathematic, product of two negative number make positive number. Test case scenario could be the product of all three positive number or two negative number * one positive number. Hope it helps


  • 0

    This one is what they want to hear.


  • 0

    @liuguiyangnwpu It's not making it clear. If you sort the nums, the code could be only 2-3 lines.


  • 0

    @vpb8262 Because the constant in O(n) is kinda big while O(logn) in O(nlogn) could be very small.


  • 0
    P

    I have the same solution, BUT don't we have the risk of min$ & max$ being the number from index i?


  • 0
    M

    same Idea in C# but with O(nlogn)

        Array.Sort(nums);
        return Math.Max(nums[nums.Length-1]*nums[nums.Length-2]*nums[nums.Length-3],
                       nums[0]*nums[1]*nums[nums.Length-1]);

Log in to reply
 

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