Product of Array Except Self — Day 33(Python)

Image for post
Image for post
Photo by Gayatri Malhotra on Unsplash

Today’s question is a favorite question among Facebook interviewers. Let us look into the question.

238. Product of Array Except Self

Given an array num of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

Constraint: It’s guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32-bit integer.

Note: Please solve it without division and in O(n).

Follow up:

Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

One of the easiest way to solve this problem to take a number, find the product of all the numbers to its left, find the product of all the numbers to its right, and the product of these two numbers is the answer. Let us look into the code snippet.

Complexity analysis

Time Complexity

The time complexity for the above solution is O(N²) where N is the number of elements in the list.

Space Complexity

The space complexity is O(N) where N is the number of elements in the list.

Can we try to improve the time complexity? Can we use lists to hold the product of elements in the left and right of each value?

Create two arrays of size same as the size of the input list. Initialize both the array with 1.

To calculate the values for the left list; Multiply each number in the list to the previous value in the left list.

To calculate the values for the right list, we start from the end of the list; Multiply each number in the list to the next value in the right list.

In the output array, multiply the elements in the left and right array.

It can be bit confusing to understand. I hope the code snippet would make it easier to understand.

Complexity analysis

Time Complexity

The time complexity for the above solution is O(N) where N is number of elements in the list.

Space Complexity

The space complexity is O(N) where N is the number of elements in the list.

Can we try to improve the space complexity? Can we try to avoid the left and right array?

Initialize the output array with a size the same as the input array with value 1.

Calculate the left side product using the same technique as the previous method.

Initialise a variable “R” which will hold the values for right product, with value as 1. For the calculating the right product, start from the end multiply with the value in the output array with R. The new value of R will be current value multiplied with value of current element in the original list.

Complexity analysis

Time Complexity

The time complexity for the above solution is O(N) where N is number of elements in the list.

Space Complexity

The space complexity is O(1) since we are not using any extra data structure for computation.

I would love to hear your feedback about my posts. Do let me know if you have any comments or feedback.

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store