Input: nums = [1,2,3]
Output: 6

Input: nums = [1,2,3,4]
Output: 24

Input: nums = [-1,-2,-3]
Output: -6

Solution Explanation for Maximum Product of Three Numbers

The problem asks to find the maximum product of any three numbers within a given integer array nums. The solution can be approached in two main ways: sorting or a single pass.

Solution 1: Sorting + Case Analysis

This approach leverages the efficiency of sorting.

Algorithm:

1. Sort: Sort the input array nums in ascending order. This allows easy access to the smallest and largest elements.

2. Case Analysis: Consider two scenarios:

   • Scenario 1 (All Non-negative or Non-positive): If all numbers are non-negative or all are non-positive, the maximum product will always be the product of the three largest numbers (the last three elements after sorting).

   • Scenario 2 (Mixed Signs): If the array contains both positive and negative numbers, the maximum product might be formed by either:

     • The product of the three largest numbers (as in Scenario 1).
     • The product of the largest number and the two smallest numbers (because the product of two negative numbers is positive).

3. Return Maximum: Compare the products from both scenarios and return the larger one.

Time Complexity: O(n log n) due to the sorting step. Space Complexity: O(log n) due to the space used by sorting algorithms (in-place sorting might reduce this to O(1) depending on implementation).

Code Examples (Python, Java, C++, Go, TypeScript): These are provided in the original response and showcase the implementation of this approach in various languages. The core logic remains consistent across all languages.

Solution 2: Single Pass

This method optimizes for speed by avoiding sorting.

Algorithm:

1. Initialization: Initialize five variables:

   • mi1, mi2: To store the two smallest numbers encountered so far.
   • mx1, mx2, mx3: To store the three largest numbers encountered so far. Initially set mi1 and mi2 to a large value (e.g., positive infinity) and mx1, mx2, mx3 to a small value (e.g., negative infinity).

2. Iteration: Iterate through the array nums. For each number x:

   • Update Minimums: If x is smaller than mi1, update mi2 to mi1 and mi1 to x. Otherwise, if x is smaller than mi2, update mi2 to x.
   • Update Maximums: If x is larger than mx1, update mx3 to mx2, mx2 to mx1, and mx1 to x. Otherwise, adjust mx2 and mx3 similarly based on x's value.

3. Return Maximum: After iterating through all numbers, calculate the products: mi1 * mi2 * mx1 and mx1 * mx2 * mx3. Return the maximum of these two products.

Time Complexity: O(n) because we iterate through the array once. Space Complexity: O(1) as we only use a constant number of variables.

Code Examples (Python, Java, C++, Go, TypeScript): These were also provided in the original response. Note that the Python version uses the heapq.nlargest and heapq.nsmallest functions for brevity, but the underlying logic remains the same as the manual update method demonstrated in Java, C++, Go and TypeScript.

Choosing the Best Solution:

The single-pass solution (Solution 2) is generally preferred due to its superior time complexity of O(n), making it more efficient for larger input arrays. Solution 1 is simpler to understand but less efficient for large datasets. The choice depends on the priorities of readability versus performance.