Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/628.html

628. Maximum Product of Three Numbers (Easy)

Given an integer array, find three numbers whose product is maximum and output the maximum product.

Example 1:

Input: [1,2,3]
Output: 6

 

Example 2:

Input: [1,2,3,4]
Output: 24

 

Note:

1. The length of the given array will be in range [3,10⁴] and all elements are in the range [-1000, 1000].
2. Multiplication of any three numbers in the input won't exceed the range of 32-bit signed integer.

 

Related Topics:
Array, Math

Similar Questions:

• Maximum Product Subarray (Medium)

Solution 1.

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public int maximumProduct(int[] nums) {
          int length = nums.length;
          Integer[] array = new Integer[length];
          for (int i = 0; i < length; i++)
              array[i] = nums[i];
          Arrays.sort(array, new Comparator<Integer>() {
              public int compare(Integer num1, Integer num2) {
                  if (Math.abs(num1) != Math.abs(num2))
                      return Math.abs(num2) - Math.abs(num1);
                  else
                      return num2 - num1;
              }
          });
          List<Integer> zeroList = new ArrayList<Integer>();
          List<Integer> positiveList = new ArrayList<Integer>();
          List<Integer> negativeList = new ArrayList<Integer>();
          for (int i = 0; i < length; i++) {
              int num = array[i];
              if (num > 0)
                  positiveList.add(num);
              else if (num < 0)
                  negativeList.add(num);
              else
                  zeroList.add(num);
          }
          int zeroCount = zeroList.size(), positiveCount = positiveList.size(), negativeCount = negativeList.size();
          if (negativeCount == 0) {
              if (positiveCount >= 3)
                  return positiveList.get(0) * positiveList.get(1) * positiveList.get(2);
              else
                  return 0;
          } else if (negativeCount == 1) {
              if (positiveCount >= 3)
                  return positiveList.get(0) * positiveList.get(1) * positiveList.get(2);
              else {
                  if (zeroCount > 0)
                      return 0;
                  else if (positiveCount >= 2)
                      return positiveList.get(positiveCount - 1) * positiveList.get(positiveCount - 2) * negativeList.get(negativeCount - 1);
                  else
                      return 0;
              }
          } else {
              int max = 0;
              if (positiveCount >= 3)
                  max = Math.max(max, positiveList.get(0) * positiveList.get(1) * positiveList.get(2));
              if (positiveCount >= 1) {
                  max = Math.max(max, positiveList.get(0) * negativeList.get(0) * negativeList.get(1));
              } else {
                  if (zeroCount > 0)
                      return 0;
                  else
                      return negativeList.get(negativeCount - 1) * negativeList.get(negativeCount - 2) * negativeList.get(negativeCount - 3);
              }
              return max;
          }
      }
  }
  
  ############
  
  class Solution {
      public int maximumProduct(int[] nums) {
          final int inf = 1 << 30;
          int mi1 = inf, mi2 = inf;
          int mx1 = -inf, mx2 = -inf, mx3 = -inf;
          for (int x : nums) {
              if (x < mi1) {
                  mi2 = mi1;
                  mi1 = x;
              } else if (x < mi2) {
                  mi2 = x;
              }
              if (x > mx1) {
                  mx3 = mx2;
                  mx2 = mx1;
                  mx1 = x;
              } else if (x > mx2) {
                  mx3 = mx2;
                  mx2 = x;
              } else if (x > mx3) {
                  mx3 = x;
              }
          }
          return Math.max(mi1 * mi2 * mx1, mx1 * mx2 * mx3);
      }
  }
  

• // OJ: https://leetcode.com/problems/maximum-product-of-three-numbers/
  // Time: O(NlogN)
  // Space: O(1)
  class Solution {
  public:
      int maximumProduct(vector<int>& A) {
          sort(begin(A), end(A));
          return A.back() * max(A[A.size() - 2] * A[A.size() - 3], A[0] * A[1]);
      }
  };
  

• class Solution:
      def maximumProduct(self, nums: List[int]) -> int:
          n = len(nums)
          nums.sort()
          return max(
              nums[0] * nums[1] * nums[n - 1], nums[n - 1] * nums[n - 2] * nums[n - 3]
          )
  
  ############
  
  class Solution(object):
    def maximumProduct(self, nums):
      """
      :type nums: List[int]
      :rtype: int
      """
      nums.sort()
      return max(nums[0] * nums[1] * nums[-1], nums[-1] * nums[-2] * nums[-3])
  
  

• func maximumProduct(nums []int) int {
  	const inf = 1 << 30
  	mi1, mi2 := inf, inf
  	mx1, mx2, mx3 := -inf, -inf, -inf
  	for _, x := range nums {
  		if x < mi1 {
  			mi1, mi2 = x, mi1
  		} else if x < mi2 {
  			mi2 = x
  		}
  		if x > mx1 {
  			mx1, mx2, mx3 = x, mx1, mx2
  		} else if x > mx2 {
  			mx2, mx3 = x, mx2
  		} else if x > mx3 {
  			mx3 = x
  		}
  	}
  	return max(mi1*mi2*mx1, mx1*mx2*mx3)
  }
  
  func max(a, b int) int {
  	if a > b {
  		return a
  	}
  	return b
  }
  

• function maximumProduct(nums: number[]): number {
      const inf = 1 << 30;
      let mi1 = inf,
          mi2 = inf;
      let mx1 = -inf,
          mx2 = -inf,
          mx3 = -inf;
      for (const x of nums) {
          if (x < mi1) {
              mi2 = mi1;
              mi1 = x;
          } else if (x < mi2) {
              mi2 = x;
          }
          if (x > mx1) {
              mx3 = mx2;
              mx2 = mx1;
              mx1 = x;
          } else if (x > mx2) {
              mx3 = mx2;
              mx2 = x;
          } else if (x > mx3) {
              mx3 = x;
          }
      }
      return Math.max(mi1 * mi2 * mx1, mx1 * mx2 * mx3);
  }
  
  

All Problems

All Solutions