DEV Community

loading...
Cover image for Maximum Product of Three Numbers

Maximum Product of Three Numbers

gkucmierz profile image Grzegorz Kućmierz ・1 min read

Platforms to practice

Leetcode problem

Implementation

const maxProduct = arr => {
  if (arr.length < 3) return false;
  const max3 = [-Infinity, -Infinity, -Infinity];
  const min2 = [Infinity, Infinity];

  for (let i = 0; i < arr.length; ++i) {
    const n = arr[i];
    if (n > max3[0]) {
      max3[0] = n;
      max3.sort((a, b) => a - b);
    }
    if (n < min2[0]) {
      min2[0] = n;
      min2.sort((a, b) => b - a);
    }
  }
  return max3[2] * Math.max(min2[0] * min2[1], max3[0] * max3[1]);
};

Complexity

Time complexity: O(n)
Space complexity: O(1)

Explanation

Loop through array, while keeping 3 max elements and 2 min elements.
We want 2 min elements because min element can have bigger absolute value. When we calculating product always 2 negative numbers give 1 positive, so we need only 2 min to check if their product is not bigger that 2 smaller numbers of our 3 max.

My github reference

https://github.com/gkucmierz/algorithms/blob/master/problems/maximum_product_of_three_numbers.js

Instacode playground

instacode.dev

Discussion (0)

pic
Editor guide