Highest Product | InterviewBit | Solution Explained

I explain the solution to Highest Product on InterviewBit using visuals in simple words.

0. Highest Product: Problem Discussion

0.0. IO Format

  • input:
    • array of N integers
  • output:
    • Highest product possible by multiplying 3 elements.
  • constraints:
    • 3 <= N <= 5e5

0.1. Examples

Input: [1, 2, 3, 4]

Output: 2 * 3 * 4 = 24

Input: [0, -1, 10, 7, 5]

Output: 5 * 7 * 10 = 350

1. Highest Product: Observations & Logic

1.0. Intuitions

At first thought, it looks like we can simply multiply the biggest 3 elements. This works well in the case [1,2,3,4] where the answer is just 2*3*4 = 24. This also works in the case [0,-1,10,5,7] giving us 5*7*10. So, this is it?

1.1. Disproving

Whenever we have a hypothesis for a solution, it is always a good idea to disprove it. If you can not find a edge-case, then the idea might be the correct one. However, if you can disprove it, don’t be sad! You just found another test case to work upon and build your observations.

Let’s take a look at some more examples:

Highest Product: test case that validates the initial thoughts
Highest Product: test case that validates the initial thoughts

This case works out perfectly. So, good going! However, what about the case below?

Highest Product: test case that invalidates the initial thoughts
Highest Product: test case that invalidates the initial thoughts

We have the wrong answer! Why? Notice how we can multiply -5 and -2 on the left to give 10 (a positive value!) and then multiply it by 5 on the right to get the correct answer of 50.

1.2. The correct logic

The above test case clearly shows that the last two negative values can be combined with a positive and it might give a better result. It is thus evident that in some cases, we have to use the logic of 2 negative and 1 positive and in some cases, we simply pick the first 3 values. Which is correct?

Well, it is impossible to know without testing both out. So, what if we simply take the max of both? Basically, we are looking at either:

  • case1: the highest 3 elements (the 3 on the right)
  • case2: the 2 lowest elements (2 negative values) and the highest positive value on the right.
  • ans = max(case1, case2)
Highest Product: case1 and case2 combined
Highest Product: case1 and case2 combined

All right! Let’s implement it.

2. Highest Product: Optimized Implementation

2.0. Code

class Solution:
# @param A : list of integers
# @return an integer
def maxp3(self, A):
        A = sorted(A)

        hi3 = A[-1] * A[-2] * A[-3]
        lo2hi1 = A[0] * A[1] * A[-1]

        return max(hi3, lo2hi1)

2.1. Complexity Analysis

  • Time: O(NlogN) to sort the array.
  • Space: O(1), to store the hi3 and lo2hi1 variables.
Avatar for Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

    Comments

    1. Please write the proof.

    2. This solution need an amendment for 2 digit number.

    3. Please write a Proof for this

    Leave a Reply

    Your email address will not be published. Required fields are marked *

    This site uses Akismet to reduce spam. Learn how your comment data is processed.