Home
Compute the Maximum Product of Three Numbers in an Array
Tags:, , ,

Compute the Maximum Product of Three Numbers in an Array

September 18, 2018 No Comments algorithms, c / c++, code, coding exercise, learn to code

Given an array of integers – find out the maximum product of the tree numbers in the array. For example, [1, 2, 3] output: [6] and [1, 2, 4, 3], output 24. We can easily write a O(n^3) algorithm that loops over three numbers and find the maximum product, however it is slow.

Sorting

If we sort the array with the complexity O(nlogn) – we know the minimal two numbers and maximum three numbers in the array. So the answer would be the maximum between min1*min2*max1 or max3*max2*max1.

1
2
3
4
5
6
7
8

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

Single Scan

We can iterative the array once and keep tracking the min1, min2, max1, max2 and max3.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        int min1 = INT_MAX, min2 = INT_MAX;
        int max1 = INT_MIN, max2 = INT_MIN, max3 = INT_MIN;
        for (int n: nums) {
            if (n <= min1) {
                min2 = min1;
                min1 = n;
            } else if (n <= min2) {     // n lies between min1 and min2
                min2 = n;
            }
            if (n >= max1) {            // n is greater than max1, max2 and max3
                max3 = max2;
                max2 = max1;
                max1 = n;
            } else if (n >= max2) {     // n lies betweeen max1 and max2
                max3 = max2;
                max2 = n;
            } else if (n >= max3) {     // n lies betwen max2 and max3
                max3 = n;
            }
        }
        return max(min1 * min2 * max1, max1 * max2 * max3);        
    }
};
class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        int min1 = INT_MAX, min2 = INT_MAX;
        int max1 = INT_MIN, max2 = INT_MIN, max3 = INT_MIN;
        for (int n: nums) {
            if (n <= min1) {
                min2 = min1;
                min1 = n;
            } else if (n <= min2) {     // n lies between min1 and min2
                min2 = n;
            }
            if (n >= max1) {            // n is greater than max1, max2 and max3
                max3 = max2;
                max2 = max1;
                max1 = n;
            } else if (n >= max2) {     // n lies betweeen max1 and max2
                max3 = max2;
                max2 = n;
            } else if (n >= max3) {     // n lies betwen max2 and max3
                max3 = n;
            }
        }
        return max(min1 * min2 * max1, max1 * max2 * max3);        
    }
};

Max product of either two numbers or three numbers:

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
402 words
Last Post: How to Sort Array By Parity?
Next Post: C++ Function to Reshape the Matrix

The Permanent URL is: Compute the Maximum Product of Three Numbers in an Array

Related posts:

  1. Algorithm to Split a Number Array into Two Balanced Parts by Using Sorting and Prefix Sum Balanced Split Given an array of integers (which may include repeated integers), determine if there’s...
  2. SQL Coding Exercise – Delete Duplicate Emails Write a SQL query to delete all duplicate email entries in a table named Person,...
  3. The USB Flash Benchmark Tool – FlashBench Previously, it is recommended that the USBCheck can be quite helpful in checking the quality...
  4. Teaching Kids Programming – Form Smallest Number From Two Digit Arrays (Set Intersection) Teaching Kids Programming: Videos on Data Structures and Algorithms Given two arrays of unique digits...
  5. Coding Exercise – Find Max Consecutive Ones Given a binary array, find the maximum number of consecutive 1s in this array. Example...
  6. Recursive Depth First Search Algorithm to Delete Leaves With a Given Value in a Binary Tree Given a binary tree root and an integer target, delete all the leaf nodes with...
  7. How to Trim a Binary Search Tree using Depth First Search Algorithm (Recursion)? Given a binary search tree and the lowest and highest boundaries as L and R,...
  8. Recursive Depth First Search Algorithm to Compute the Sum of Nodes with Even-Valued Grandparent in a Binary Tree Given a binary tree, return the sum of values of nodes with even-valued grandparent. (A...

Leave a Reply