CODEWITHSUNDEEP
pythonalgorithmdata-structuresinitialization
mourinho
mourinho

Reputation: 783

Max product of 3 integers in an array

I am trying to solve a problem where I want to find the max product of any 3 integers in an array.

I tried my solution:

def maximumProduct(nums):
    """
    :type nums: List[int]
    :rtype: int
    """

    list_of_ints = nums

    t = sorted(list_of_ints[:4])

    max_pos = t[2] 
    max_pos_2 = t[1]
    max_pos_3 = t[0]

    min_neg = 0
    min_neg_2 = 0

    for x in list_of_ints[3:]:
        if x<0 and x< min_neg:
            temp = min_neg
            min_neg = x
            min_neg_2 = temp

        elif x<0 and x<min_neg_2: 
            min_neg_2 = x

        if x>0 and x>max_pos:
            temp = max_pos
            max_pos = x
            temp2 = max_pos_2
            max_pos_2 = temp
            max_pos_3 = temp2

        elif x>0 and x>max_pos_2:
            temp = max_pos_2
            max_pos_2 = x
            max_pos_3 = temp

        elif x>0 and x>max_pos_3:
            max_pos_3 = x

    return max(max_pos*max_pos_2*max_pos_3, min_neg*min_neg_2*max_pos)

The above solution fails on input nums = [-1, -2, -3]. The expected output is -6, the output of the program is 0.

This is due to the initialization of min_neg and min_neg_1 to zero.

How to initialize to avoid this issue? I always have trouble setting up the right initializations.

Upvotes: 1

Views: 1676

Answers (5)

oc0dedata
oc0dedata

Reputation: 1

I tried kfx's O(n) solution but it was not taking into account possible negative ints for me. I added a few lines to adjust for that, and also two more possible combinations and it worked. Correct me if I am wrong but I think this is still O(n) notation right?

def maximum_product(nums): 
    max3 = heapq.nlargest(3, nums)
    min3 = heapq.nsmallest(3, nums)
    a1 = max3[0] * max3[1] * max3[2]
    a2 = min3[0] * min3[1] * min3[2]
    a3 = min3[0] * max3[0] * max3[1]
    a4 = min3[0] * min3[1] * max3[0]
    if abs(min(a1, a2, a3, a4)) > abs(max(a1, a2, a3, a4)):
        return min(a1, a2, a3, a4)
    else:
        return max(a1, a2, a3, a4)

Upvotes: 0

kfx
kfx

Reputation: 8537

Approach

To solve this kind of exercise efficiently, you need to recognize that there are only a few possible cases. Focus on the signs of the numbers and think what would be the sign of the result:

+ * + * + = +  (good)
+ * + * - = -  (bad)
+ * - * - = +  (good)
- * - * - = -  (bad)
anything * 0 = 0 (neutral)

So, if the list has both negative and negative numbers, the answer is either the product of the three largest numbers, or the product the two smallest (negative) numbers and the largest number (positive).

If this condition is not true, the answer must be the product of the largest numbers in the array.

O(n log (n)) solution

So, the answer has to take either the three last elements in the array after sorting, or the two first ones and the last one, and multiply them together. The simplest and most elegant way to do it is to first sort the list of numbers:

def maximum_product(nums): # O(n log(n)) solution
   nums.sort()
   assert len(nums) >= 3 # assume the input has been validated
   a1 = nums[-1] * nums[-2] * nums[-3]
   a2 = nums[0] * nums[1] * nums[-1]
   return max(a1, a2)

O(n) solution

However, you can also find the maximal three and the minimal two numbers in O(n) time. One efficient approach how to find the maximum N numbers in a container is to keep a heap of size N while iterating through it. At the end, the heap contains the answer: a partially sorted list of N largest elements.

Python module heapq offers convenient API for this: the functions nlargest() and nsmallest(). So here we go:

import heapq

def maximum_product(nums): # O(n) solution
   assert len(nums) >= 3 # assume the input has been validated
   max3 = heapq.nlargest(3, nums)
   min2 = heapq.nsmallest(2, nums)
   a1 = max3[0] * max3[1] * max3[2]
   a2 = min2[0] * min2[1] * max(max3)
   return max(a1, a2)

Upvotes: 5

martineau
martineau

Reputation: 123541

You can use itertools.combinations to make doing it very easy. What you're calling an "array" is referred to as a "list" in Python, by-the-way.

from itertools import combinations

def maximum_product(nums):
    return max(trio[0] * trio[1] * trio[2] for trio in combinations(nums, 3))

nums = [-1, -2, -3, 9]
print(maximum_product(nums))  # -> 54

This could be generalized to determine the maximum product of N integers by (also) using functools.reduce() to compute the product of N items:

from functools import reduce
from itertools import combinations

def maximum_product(nums, group_size):
    return max(reduce(lambda a, b: a*b, nums, 1)
                    for group in combinations(nums, group_size))

nums = [-1, -2, -3, 9]
print(maximum_product(nums, 3))  # -> 54

Of course, this generality will slow execution down a bit...

Upvotes: 1

Adi219
Adi219

Reputation: 4814

Try this:

arr = sorted(list_of_ints)

def getMax(t):

    maxP = t[0] * t[1] * t[2]

    i = 0
    while t[i] > -1:
        i += 1

    maxN = t[i] * t[i + 1] * t[0]

    return max(maxP, maxN)

print(getMax(arr))

Upvotes: 0

Chris Noyes
Chris Noyes

Reputation: 56

You can initialize to negative infinity: min_neg = float('-inf')

Upvotes: 2

Related Questions