Max Product of Three Numbers in Linear Time and No Extra Space

Fun problem by Facebook, via Daily Coding Problem:

This problem was asked by Facebook.
Given a list of integers, return the largest product that can be made by multiplying any three integers.
For example, if the list is [-10, -10, 5, 2], we should return 500, since that's -10 * -10 * 5.
You can assume the list has at least three integers.

Clearly there is an O(n^3) solution, and with a little more analysis you can reduce that to O(nlogn) by sorting and analyzing the extremities.

There is a better solution, though. It has to do with the "product of three numbers". There are two cases to consider:

a) Either the maximum product will be the product of the 3 largest numbers. I think that it is straightforward to see that, especially if the numbers are all positive. Even if they are all negative, the product of the 3 largest will give you the right answer.
b) Or, the maximum product will be the product of the 2 smallest numbers and the largest number. This happens when the bottom 2 are negative numbers, whose product will be a large positive number.

And that's it. Hence you can find the 5 numbers above (top 3, bottom 2) in linear time and return the max between (a) and (b).

Happy Thanksgiving!!!
Boris

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DailyCodingProblem
{
 class DailyCodingProblem11222018
 {
  public int Max3(int[] numbers)
  {
   int top1 = Int32.MinValue;
   int top2 = Int32.MinValue;
   int top3 = Int32.MinValue;
   int bottom1 = Int32.MaxValue;
   int bottom2 = Int32.MaxValue;

   for (int i = 0; i < numbers.Length; i++)
   {
    GetTop3Max(numbers[i], ref top1, ref top2, ref top3);
    GetBottom3Min(numbers[i], ref bottom1, ref bottom2);
   }

   return Math.Max(bottom1 * bottom2 * top1, top1 * top2 * top3);
  }

  private void GetTop3Max(int n,
        ref int top1,
        ref int top2,
        ref int top3)
  {
   if (n >= top1)
   {
    top3 = top2;
    top2 = top1;
    top1 = n;
   }
   else if (n >= top2)
   {
    top3 = top2;
    top2 = n;
   }
   else if (n >= top3)
   {
    top3 = n;
   }
  }

  private void GetBottom3Min(int n,
           ref int bottom1,
           ref int bottom2)
  {
   if (n <= bottom1)
   {
    bottom2 = bottom1;
    bottom1 = n;
   }
   else if (n <= bottom2)
   {
    bottom2 = n;
   }
  }
 }
}

Comments

  1. A great combination of analytical thinking and careful implementation. The only thing I can add is that it's technically possible to use a slightly more efficient version of finding 3 highest and 2 lowest numbers (based on a pairwise comparison of elements in the array) and you have a typo in GetBottom3Min which should be GetBottom2Min :) Also, these kinds of methods always remind me about how awesome to have languages like Go or Python that have native tuple support.

    ReplyDelete
  2. Replies
    1. Thank you! I've recently started to appreciate posts that describe thought process even more - on top of giving a unique insight into your methodology, since it's in a written form it's much easier to analyze and think about how I can use it improve my own.

      Delete

Post a Comment

Popular posts from this blog

Count Binary Substrings

Count Vowels Permutation: Standard DP

Maximum Number of Balloons