[LeetCode] 238. Product of Array Except Self

Table of Content

Problem Statement
Problem Input
Solution

Problem statement

Given an array nums 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].

Input

Example

Input:  [1,2,3,4]
Output: [24,12,8,6]

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.)

Solution

Source code

Time Complexity: O(N)

Space Complexity: O(N)

The straightforward solution to this problem is to just take the product of the array and divide it by the excluded value to obtain the product except itself. However, we’re explicitly disallowed from using this method.

The idea behind this problem is to create an alternative method to division. To do so, we can split the array into two sub-arrays with the excluded index as our divider. However, since we only care about the product of the sub-arrays, we can just store their accumulating sum. Then we’ll calculate the product of those two sub arrays and multiply them together.

For example, here’s what it’ll look like visually:

Input: [1,2,3,4,5,6]

Splitting...
| 2 3 4 5 6,
1 | 3 4 5 6
1 2 | 4 5 6
...
1 2 3 4 5 |

#Note that in the algorithm, we use 1 as a filler for the case when there is no number on one side of the divider.
First_split:  [1, 1, 2, 6, 24, 120]
Second_split: [720, 360, 120, 30, 6, 1]
Result:       [720, 360, 240, 180, 144, 120]

class Solution:
  def productExceptSelf(self, nums: List[int]) -> List[int]:
    length = len(nums)
    # We initialize two arrays ofsame size of the input array to keep track of our split multiplication.
    # first_split is used to store the accumulating sum of the left sub array.
    # second_split is used to store the accumulating sum of the right sub array.
    first_split = [ None] * length
    second_split = [ None ] * length
    result = [ None ] * length
    # We use 1 here since anything multiply by 1 is itself.
    # second_split is the reverse version of first_split, since the length of the right sub array will always be the total length - the size of the left sub array.
    # Therefore we set 1 at second_split's end instead.
    first_split[0], second_split[length - 1] = 1, 1

    for i in range(1, length):
      # The next value in first_split is the the previous value in first_split * the input's previous value.
      first_split[i] = first_split[i - 1] * nums[i - 1]
      # second_split does the reverse of whatever first_split does.
      second_split[length - i - 1] = second_split[length - i] * nums[length - i]

    for i in range(length):
      result[i] = first_split[i] * second_split[i]
    return result

Complexity Explanation

Time complexity is O(N) because we’re iterating through the entire input array.

Since we introduced two new arrays to hold the split sub-arrays, the space complexity is O(2N) or just O(N).

Optimized solution

Source code

Time Complexity: O(N)

Space Complexity: O(1)

However, we can also achieve the same result without creating two arrays. Instead of tracking the accumulating sum inside an array, we’ll just track the accumulating sum itself by combining all the logic into the same iteration.

class Solution:
  def productExceptSelf(self, nums: List[int]) -> List[int]:
    length = len(nums)
    result = [ 1 ] * length
    # Use an accumulating sum instead of an accumulating array
    first_split = 1
    second_split = 1

    # We essentially converted the algorithm above to work with our accumulating sum.
    for i in range(0, length):
      # Update the result before we modify our accumuluating sum.
      result[i] *= first_split
      first_split *= nums[i]
      # Same here, except in reverse.
      result[length - 1 - i] *= second_split
      second_split *= nums[length - 1 - i]

    return result

Complexity Explanation

Time complexity is the same since the overall method didn’t change.

However, the space complexity is now O(1) because we removed the unnecessary arrays.