MaxProductOfThree in C#

Question

This is my solution for the MaxProductOfThree from codility, it scores 100%, but I'm not a fan of the if if if structure it has going on.

Task description

---

A non-empty array A consisting of N integers is given. The product of triplet (P, Q, R) equates to A[P] * A[Q] * A[R] (0 ≤ P < Q < R < N).

For example, array A such that:

A[0] = -3 A[1] = 1 A[2] = 2 A[3] = -2 A[4] = 5 A[5] = 6 contains the following example triplets:

(0, 1, 2), product is −3 * 1 * 2 = −6 (1, 2, 4), product is 1 * 2 * 5 = 10 (2, 4, 5), product is 2 * 5 * 6 = 60 Your goal is to find the maximal product of any triplet.

Write a function:

class Solution { public int solution(int[] A); }

that, given a non-empty array A, returns the value of the maximal product of any triplet.

For example, given array A such that:

A[0] = -3 A[1] = 1 A[2] = 2 A[3] = -2 A[4] = 5 A[5] = 6 the function should return 60, as the product of triplet (2, 4, 5) is maximal.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [3..100,000]; each element of array A is an integer within the range [−1,000..1,000].

using System;
using System.Collections.Generic;
using System.Linq;

class Solution {
    public int solution(int[] A) 
    {
        List<int> B = A.ToList();
        int product = 1;
        int min1 = B.Min();
        if (A.Length > 3)
        {
            if (min1 < 0)
            {
                B.RemoveAt(B.IndexOf(min1));
                int min2 = B.Min();
                if (min2 < 0)
                {
                    int max1 = B.Max();
                    if (A.Length == 4)
                    {
                        product = min1 * min2 * max1;
                    }
                    else
                    {
                        product = Math.Max(min1 * min2 * max1, getProductOfMaximalsForMoreThanTwoElements(B));
                    }
                }
                else
                {
                    product = getProductOfMaximalsForMoreThanTwoElements(B);
                }
            }
            else
            {
                product = getProductOfMaximalsForMoreThanTwoElements(B);
            }
        }
        else
        {
            foreach (int element in B)
            {
                product *= element;
            }
        }
        return product;
    }

    private int getProductOfMaximalsForMoreThanTwoElements( List<int> B)
    {
        int max1 = B.Max();
        B.RemoveAt(B.IndexOf(max1));
        int max2 = B.Max();
        B.RemoveAt(B.IndexOf(max2));
        int max3 = B.Max();
        return max1 * max2 * max3;
    }
}

To be honest, the original idea was thought beforehand, but it took me a couple of tries until every test was passed, as with most of these exercises. Are there things to improve in terms of readability, logic and quality of this code?

Answer 1

This looks like a good attempt. Let's first start assuming we only have to deal with positive values.

private int getProductOfMaximalsForMoreThanTwoElements( List<int> B)
{
    int max1 = B.Max();
    B.RemoveAt(B.IndexOf(max1));
    int max2 = B.Max();
    B.RemoveAt(B.IndexOf(max2));
    int max3 = B.Max();
    return max1 * max2 * max3;
}

This method would provide the solution. So let's review it.

Starting with a couple of style choices, method names in C# should be PascalCase. Additionally, the name of the method is vague. The method provides the product of the 3 biggest numbers: GetProductOfTop3Numbers.

B.IndexOf(B.Max()) is doing unnecessary work. Max loops over the entire list to find the maximum value, and IndexOf does it all over again. That's a waste of effort. Sadly, System.Linq doesn't provide an ArgMax method, so we will have to spin our own:"

public static int ArgMax(this IList<int> list) {
  var max = int.MinValue;
  var argmax = -1;
  var index = 0;
  foreach(var item in list) {
    if (item > max) {
      max = item;
      argmax = index;
    }
    index++;
  }
  return argmax;
}

Here, instead of looping through the list to find the maximum value, and then search the list for that value, we can just return the index we found that biggest value at. The max is then easily retrievable through B[index].

The act of searching the list for the max, and popping it can be its own method:

public static int PopMax(List<int> list)
{
  var argmax = list.ArgMax();
  var max = list[argmax];
  list.RemoveAt(argmax);
  return max;
}

Our initial method would then be:

private static int GetProductOfTop3Numbers(List<int> list) {
  var product = 1;
  product *= PopMax(list);
  product *= PopMax(list);
  product *= PopMax(list);
  return product;
}

Or, more generic:

private static int GetProductOfTopNNumbers(List<int> list, int n) {
  var product = 1;
  for(var times = 0; times < n; times++) {
    product *= PopMax(list);
  }
  return product;
}

---

Now let's return to the actual problem: negative numbers. This is what caused you problems introducing a bunch of if-statements. Let's see if we can find something for that.

We want the highest possible product. If we simply take the top 3 items from the list, we might risk missing out on very negative numbers. Take for instance the list new [] { -5, -5, -3, -1, 0, 1, 2, 3 }. In this case, the naive solution would be 1 * 2 * 3, but actually -5 * -5 * 3 has a bigger product. Note that if we consider negative numbers in our solution, it will always have to be a pair of negative numbers, to cancel out the - signs.

This pair would then always be the two lowest entries in the list. The two most negative numbers together should provide the biggest product out of all negative numbers. The product of these can then be compared to the product of the biggest numbers, to decide which of the two sets to pick.

Furthermore, because we will never take 3 negative numbers (because the product would be negative), we can freely take the biggest number in the list. Should this number also be negative (because the input only consists of negative numbers), this is fine as well, because it would then be the least negative number, which still would result in the biggest product.

So, to recap:

1. Take the biggest number
2. Take the next two biggest numbers, or take the next two smallest numbers
3. Check which together has the biggest product
4. Done

For the mins, we need to provide a similar ArgMin and PopMin implementations. Also realise that simultaneously popping items from the list at both ends might cause troubles if this list is very short, so be sure to copy the list:

private static int GetProductOfTopNNumbers(List<int> list, int n) {
  var copiedList = new List<int>(list);
  var product = 1;
  for(var times = 0; times < n; times++) {
    product *= PopMax(copiedList);
  }
  return product;
}

All in all, that leaves us with:

public int Solution(int[] A) {
  var list = A.ToList();
  var max = PopMax(list);
  return Math.Max(max * GetProductOfMinNNumbers(list, 2), max * GetProductOfTopNNumbers(list, 2));
}

public static int ArgMin(this IList<int> list)
{
  var min = int.MaxValue;
  var argmin = -1;
  var index = 0;
  foreach (var item in list)
  {
    if (item < min)
    {
      min = item;
      argmin = index;
    }
    index++;
  }
  return argmin;
}

public static int PopMin(List<int> list)
{
  var argmin = list.ArgMin();
  var min = list[argmin];
  list.RemoveAt(argmin);
  return min;
}

private static int GetProductOfMinNNumbers(List<int> list, int n)
{
  var copiedList = new List<int>(list);
  var product = 1;
  for (var times = 0; times < n; times++)
  {
    product *= PopMin(copiedList);
  }
  return product;
}

Answer 2

Since its multiplication, the largest possible product could only be produced by multiplying the largest numbers in the array. However, negative numbers introduce a problem, as a product of 2 negative numbers with a positive one would end up being positive too. Hence, we need to consider both cases in our solution. I would like to propose the following solution to this problem:

using System;
using System.Collections.Generic;
using System.Linq;

class Solution {
    public int solution(int[] A) 
    {
        Array.Sort(A); // Simple sort of the array
        int len = A.Length;
        int end = A[len - 1] * A[len - 2] * A[len - 3]; // Find the largest product of positive numbers
        int start = A[0] * A[1] * A[len - 1]; // Find the largest product, assuming 2 negative numbers

        return (start > end) ? start : end;
    }
}

In this code, we first calculate the first case, since the last 3 indices should contain the largest integers in the list, resulting in the highest product. We then calculate the second case, taking the largest number and the 2 smallest ones, which should produce a positive product if the largest number is positive and the 2 smallest are negative. Finally, we take the larger of the 2.