238 — Product of Array Except Self

Problem Statement

Restating Info We’re Already Given:

• We’re given an integer array with a length anywhere between 2 and 100,000 inclusive.
• Each of the integers is limited to between -30 and 30.
• No integer overflow will occur since each prefix/suffix fits in a 32-bit integer. (I’m using Python so doesn’t matter in this specific case)

Questions/Clarifications to Possibly Ask Interviewer (If starting information we’re given isn’t sufficient to begin):

• N/A

Discuss Naive Solution:

We can enumerate out 2 arrays to represent the product of the values to the left and to the right of all indices. We multiply them together to get the output. This can be done in linear time with linear space (1 additional array of length equal to the inputted array).

Code Naive Solution:

Discuss Optimal Solution:

The runtime complexity is as fast as possible. However, we can save space. To do so, we can replace the suffix product array with a suffix product variable. Going in reverse, we instead only store the value we need for the current index as the other values are of no use.

Code Optimal Solution:

Runtime/Space Complexity:

The optimal solution runs in linear time and uses constant space now that we use a variable to represent the most recent accumulated value for the suffix product.

Test Cases:

• Length 2 array
• Length 100,000 array
• Array with all negative numbers
• Array with all positive numbers
• Array with negative and positive numbers