Problem Explanation

This problem requires us to maxmize the product by choosing any three numbers from an array of integers. The array can include positive and negative numbers. Negative numbers can produce a positive product when multiplied with another negative number. Therefore, to get the maximum product, we either use the largest three numbers, or the largest one and the smallest two (if they are negative).

Let's walk through an example for better understanding.

Suppose our array is [-10, -10, 1, 2, 4]

In this case, maximum product can be obtained by multiplying the largest number i.e., 4 with the two smallest numbers i.e., -10 and -10. Hence, the maximum product will be -10*-10*4 = 400.

Solution Approach

The approach of the solution is to first sort the array of integers. Then calculate the product of the largest three numbers and the product of the smallest two numbers and the largest one. The maximum of these two products will be our result.

In the above example, after sorting the array will be: [-10, -10, 1, 2, 4]

Largest three numbers are: 4, 2, 1. Their product is 421 = 8.

Smallest two numbers and the largest one are: -10, -10, 4. Their product is -10*-10*4 = 400.

Maximum of these two products is 400. Thus, our result will be 400.

Solution

Python Solution

1
2python
3class Solution:
4    def maximumProduct(self, nums):
5        nums.sort()
6        return max(nums[-1] * nums[0] * nums[1], nums[-1]*nums[-2]*nums[-3])

Java Solution

1
2java
3class Solution {
4    public int maximumProduct(int[] nums) {
5        Arrays.sort(nums);
6        int n = nums.length;
7        return Math.max(nums[n - 1] * nums[0] * nums[1], nums[n - 1] * nums[n - 2] * nums[n - 3]);
8    }
9}

JavaScript Solution

1
2javascript
3var maximumProduct = function(nums) {
4    nums.sort((a, b) => a - b);
5    let n = nums.length;
6
7    return Math.max(nums[n - 1] * nums[0] * nums[1], nums[n - 1] * nums[n - 2] * nums[n - 3]);
8};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int maximumProduct(vector<int>& nums) {
6        sort(nums.begin(), nums.end());
7        int n = nums.size();
8        return max(nums[n - 1] * nums[0] * nums[1], nums[n - 1] * nums[n - 2] * nums[n - 3]);
9    }
10};        

C# Solution

1
2csharp
3public class Solution {
4    public int MaximumProduct(int[] nums) {
5        Array.Sort(nums);
6        int n = nums.Length;
7        return Math.Max(nums[n - 1] * nums[0] * nums[1], nums[n - 1] * nums[n - 2] * nums[n - 3]);
8    }
9}

In all of these solutions, we are first sorting the array and then getting the maximum product by comparing two products: one is the product of the largest three numbers and other is product of smallest two and the largest one.# Time Complexity

In all of the above given solutions, the operations performed are linear, except for the sorting operation. The time complexity of the sorting operation will be the dominating factor in these solutions.

If we are using a comparison-based sorting algorithm, the time complexity can range from O(n log n) to O(n^2), depending on the specific sorting algorithm used, where n is the number of elements in the array.

Python’s sort function, Java's Arrays.sort(), JavaScript's sort(), C++'s sort() and C#'s Array.Sort() are based on comparison sorting algorithm, typically quicksort, heapsort, mergesort or timsort, thus these implementations would have a worst-case and average time complexity of O(n log n).

Space Complexity

The space complexity for all the solutions is O(1), which means it uses constant extra space because the sorting is happening in place and no additional data structures are being used.

This doesn't take into account the stack space used for recursion in the sorting algorithms coded into the languages. If recursions are taken into account then the space complexity would be O(log n) as quicksort (which these languages usually use) has a space complexity of O(log n).

In conclusion, these solutions are not only concise and easy to understand but are also efficient with a time complexity of O(n log n) and a space complexity of O(1) (considering only the extra space used). They effectively solve the problem by leveraging the technique of sorting and then choosing the appropriate numbers based on the problem’s requirements. Working with the sorted array makes the logic for selecting the numbers to multiply very straightforward.