Maximum Product of Three Numbers

Given an integer array nums, we need to find three numbers in the array whose product is maximum and return that maximum product.

Approach

To maximize the product, we should consider both positive and negative numbers, as the product of two negative numbers can be positive.

  1. Sort the Numbers: First, we sort the array to easily access the largest and smallest numbers.

  2. Consider Cases: There are two main cases that we must consider to find the maximum product:

    • Three Largest Numbers: The product of the three largest numbers in the array.
    • Two Smallest and One Largest Number: If there are negative numbers, the product of the two smallest numbers (which can be negative) and the largest number.

  3. Return Maximum Product: Return the maximum of the above two cases.

Code

Here’s the Python code:

1
2
3
4

class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        nums.sort()
        return max(nums[-1] * nums[-2] * nums[-3], nums[0] * nums[1] * nums[-1])

Examples

  • Example 1: nums = [1,2,3], the output will be 6, as the product of the three largest numbers is the maximum.
  • Example 2: nums = [1,2,3,4], the output will be 24, as the product of the three largest numbers 2, 3, 4 is the maximum.
  • Example 3: nums = [-1,-2,-3], the output will be -6, as the product of the three largest numbers is the only option here.

Insight

This problem illustrates the importance of considering edge cases and utilizing sorting to simplify the solution. By handling both positive and negative numbers properly, we ensure that the solution is both simple and correct.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        smallestTwo = [float('inf')]*2
        largestThree = [float('-inf')]*3
        for num in nums:
            if num <= smallestTwo[0]:
                smallestTwo[0] = num
                smallestTwo.sort(reverse=True)
            if num >= largestThree[0]:
                largestThree[0] = num
                largestThree.sort()
        return max(smallestTwo[0]*smallestTwo[1]*largestThree[2], 
                   largestThree[0]*largestThree[1]*largestThree[2])

Problem Classification

This problem is rooted in the domain of “Mathematics” and “Array manipulation”. The task revolves around numerical operations, specifically multiplication and comparison to find the maximum product, and uses an array as the fundamental data structure.

Problem Components Analysis:

  1. Integer Array: An array of integers serves as the input. This means the problem involves dealing with sequence data, and each element can be a positive, negative, or zero integer.

  2. Three Numbers: The problem requires identifying three numbers from the given array. This introduces a degree of combination selection.

  3. Product: The task involves calculating the product of the three numbers, indicating the use of multiplication arithmetic.

  4. Maximum: The goal is to find the maximum possible product from all the combinations of three numbers. This involves the process of comparison to determine the maximum.

The problem can be classified as an “Optimization” problem, specifically under the “Combinatorial Optimization” category. It requires exploring different combinations of three numbers from the array to optimize (maximize) a specific objective function (in this case, the product of the three numbers).

Language Agnostic Coding Drills

1. Dissection of the Code into Distinct Concepts:

a. Class and Function Declaration: The given code defines a class Solution and a function maximumProduct within it. This involves the concept of defining classes and functions.

b. Array Manipulation: The code creates and manipulates two arrays, smallestTwo and largestThree. This involves the creation of arrays, assignment of elements, and sorting.

c. Looping Through Arrays: The code uses a for loop to traverse through the nums array. This involves understanding iterative structures.

d. Condition Checking: There are two if conditions within the loop. This introduces the concept of conditional statements and Boolean logic.

e. Mathematical Operations: The code calculates products of elements in an array and compares these products to find the maximum. This requires knowledge of arithmetic operations and comparison operations.

2. Concepts in Increasing Order of Difficulty:

a. Class and Function Declaration: This is a basic concept in almost all programming languages. One needs to understand the syntax and how to structure a class and function. But once learned, this concept is fairly straightforward.

b. Array Manipulation: This concept requires understanding how to declare an array, assign values to array elements, and manipulate array data (e.g., sorting). Although not overly complex, it builds upon the basic understanding of variables and data types.

c. Looping Through Arrays: This concept involves using loops to traverse each element in an array. It’s a fundamental concept, but when combined with array manipulation, it can become a bit more complex.

d. Condition Checking: Although basic in isolation, condition checking can become complex when nested or combined with other concepts like looping and array manipulation.

e. Mathematical Operations: While basic arithmetic operations are straightforward, using them in conjunction with arrays, loops, and conditions to find the maximum product can be challenging.

3. Problem-Solving Approach:

The problem is essentially about finding three numbers from the given array that give the maximum product. This can be done by keeping track of the three largest and two smallest numbers (as the product of two negatives becomes a positive).

To approach this, the code first initializes two arrays, one to store the two smallest numbers and the other to store the three largest numbers. The code then iterates through each number in the given array, updating the two arrays as it encounters a number smaller or larger than the currently stored numbers.

Finally, the code calculates the maximum of two possible products: one from the product of the three largest numbers, and the other from the product of the two smallest numbers and the largest number. This final comparison is necessary because the two smallest numbers might be negative, and their product could become positive, thus possibly leading to a larger product when multiplied by the largest number.

Targeted Drills in Python

1. Python Coding Drills for Each Identified Concept:

a. Class and Function Declaration:

1
2
3

class ExampleClass:
    def exampleFunction(self):
        pass

This simple drill demonstrates how to declare a class and a function in Python.

b. Array Manipulation:

1
2
3

array = [5, 3, 7, 2]
array.sort()
print(array)  # prints: [2, 3, 5, 7]

This drill illustrates how to declare an array, sort its elements, and print the array.

c. Looping Through Arrays:

1
2
3

array = [1, 2, 3, 4, 5]
for i in array:
    print(i)

This drill goes through each element in an array and prints it.

d. Condition Checking:

1
2
3
4
5

number = 5
if number > 3:
    print("Greater")
else:
    print("Not greater")

This drill checks whether a number is greater than a certain value and prints a message based on the result.

e. Mathematical Operations:

1
2
3
4
5

a = 5
b = 3
c = 2
product = a * b * c
print(product)  # prints: 30

This drill calculates the product of three numbers and prints the result.

2. Problem-Specific Python Coding Drills:

For this problem, we also need to handle the concept of maintaining the three largest and two smallest numbers in an array while iterating through the array. This concept can be illustrated through the following drill:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

nums = [1, -2, 3, -4, 5]
smallest_two = [float('inf')] * 2
largest_three = [float('-inf')] * 3

for num in nums:
    if num <= smallest_two[0]:
        smallest_two[0] = num
        smallest_two.sort(reverse=True)
    if num >= largest_three[0]:
        largest_three[0] = num
        largest_three.sort()

print(smallest_two)  # prints: [-4, -2]
print(largest_three)  # prints: [3, 5, 1]

This is essential for our problem because we need to keep track of the three largest and two smallest numbers to calculate the maximum product of three numbers.

3. Assembling the Final Solution:

The final solution is created by integrating all the above concepts. We first declare a class and a function. Inside this function, we declare and initialize two arrays to keep track of the smallest and largest numbers.

We then loop through the given array, updating our smallest and largest number arrays as we go. This involves using both condition checking (to determine if a number should replace the current smallest or largest number) and array manipulation (to replace the number and then re-sort the array).

Finally, we calculate and return the maximum product of three numbers. This involves a combination of array manipulation (to access the specific numbers we need) and mathematical operations (to calculate the products and find the maximum). The result is returned as the output of the function.