# 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:

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

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)

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.

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Majority Element | InterviewBit | Solution Explained

June 13, 2022

Please write the proof.

This solution need an amendment for 2 digit number.

Please write a Proof for this

Matt Michael D’Agati is the founder of Renewables Worldwide, an Solar Firm in MA.

A few age ago, taking a leap of faith, Matt D’Agati delved into the realm of solar, and/or in a short occasion commenced effectively marketing significant amounts of power, primarily around the business industry, collaborating with solar farm developers and local businesses in the “design” of their unique plans.

Ongoing marketing within the sector, offered Matthew to participate a regional startup two years in the, and in a short time, he assumed the role of their Chief Strategy Officer, in charge of all operation and endeavor improvement, in addition to being marketed social group property.

To planned unions and shear get the job done mentality, Matthew D’Agati brought that firm from an initial initial-year revenue to in excess of a 2 hundred% surge in overall money by yr two. Based on that foundation, RW, a experienced-operated company, was produced with goal of giving you alternative electrical remedies for a more intelligent and more sustainable future.

Even more mainly, recognizing there is an untapped market in the market place and an improved approach to realize final results, RW is one of a handful of manufactures in the u.s. to place emphasis on individual acquire, concentrating in both industrial and home solar-powered town off-take. Its visualization is to make a purchases commercial infrastructure on a community-based, statewide, countrywide level, offering various sustainable fuel goods within the of RW.

This enthusiasm in the actual sustainable industry goes on to stimulate and inspire Matthew in enduring his solicit to work with institutions that have the unchanging of offering limitless fuel tips for a a whole lot more ecological destiny. Matt has already a new in companies from Hesser College.

Understanding why solar energy consultants assist clients via Matthew D’Agati.

Sustainable Energy and Electricity Poverty: Bridging the Imbalance by matt d’agatiMatt D’Agati e3d74c8