# Highest Product of X Items

🧩 How do you find the highest product of X items?

This should optimize for runtime complexity and protect from overflows from large products.

• Inputs
1. An array of both positive and negative Ints representing potential products to the solution
2. An Int representing the number of products required for the solution
• Output: An Int representing the highest product of X amount of numbers.

For example, for the highest product of 3 items, the input is iterated through while updating the following variables. After the iteration has completed in $$O(n)$$ time, the highest product of three variable is returned as the solution.

• Lowest number
• Highest number
• Lowest product of two
• Highest product of two
• Highest product of three
• Are the input numbers positive? Why isn't this just the product of the $X$ largest input numbers? – Steven Dec 3 '20 at 17:12
• Steven, thanks for the comment. I've updated the post to indicate that the input can be both positive and negative numbers. – Adam Hurwitz Dec 4 '20 at 14:17

Let the integers be $$a_1,a_2,\dots,a_n$$ sorted in decreasing order of magnitude, so $$|a_1| \ge |a_2| \ge \cdots$$, and suppose you want to find the product of $$k$$ of them that is as large as possible.

Then:

• If $$a_1 \times \cdots \times a_k$$ is positive, it is the solution.

• Otherwise, if $$a_{k+1}$$ is positive, the solution is $$a_1 \times \cdots \times a_{k+1}$$ (but omit $$a_i$$ from the product, where $$a_i$$ is the largest of the negative numbers in $$a_1,\dots,a_k$$, i.e., closest to zero).

• Otherwise, if $$a_{k+1}$$ is negative and at least one of $$a_1,\dots,a_k$$ is positive, the solution is $$a_1 \times \cdots \times a_{k+1}$$ (but omit the smallest positive number of $$a_1,\dots,a_k$$ from the product).

• Otherwise, if at least one of $$a_1,\dots,a_n$$ is positive, the solution is $$a_1 \times \cdots \times a_{k-1} \times a_j$$ where $$a_j$$ is the largest positive number in $$a_1,\dots,a_n$$.

• If all of $$a_1,\dots,a_n$$ are negative and $$k$$ is odd, then the solution is $$a_{n-k+1} \times \dots \times a_n$$.

This can be computed in $$O(n \lg k)$$ time using a heap of size $$k$$.

• @Dmitry, good point! I've revised my answer. I hope I've covered all the cases now. – D.W. Dec 5 '20 at 21:06

Time Complexity: $$O(nlogn)$$

Space Complexity: $$O(n)$$

1. Sort the $$input$$ array.

2. If the last item is positive, find the product for the first $$n$$ items.

3. If the last item is negative, count how many $$negativeItems$$ exist up to $$n$$, and then round the number, $$negativeItems$$, down to the closest even number.

4. Starting with the smallest negative item, compare it to the largest item at the beginning of the $$input$$ array. Then compare the next largest negative item with the second-largest item, and so forth until all $$negativeItems$$ are compared.

4a. Add the original value of the result of whichever number contains the greater absolute value into the $$productArray$$.

4b. Add the remaining positive items, $$n - negativeItems$$, to the $$productArray$$.

5. Calculate the product from the $$productArray$$.