Katkat
Back

Product of Array Except Self Without Division

NewrelicSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests array manipulation skills and the ability to optimize space complexity by using prefix and suffix product passes instead of division.

Problem Statement

Given an array of integers nums, return an array result such that result[i] is equal to the product of all the elements of nums except nums[i].

You must solve this challenge without using the division operator and in O(n) time complexity.

Requirements

  • The input array nums will have a length between 2 and 10^5.
  • Each element nums[i] is an integer between -10 and 10.
  • The product of any prefix or suffix will fit in a 64-bit signed integer.
  • You must achieve O(1) auxiliary space (the output array does not count toward this limit).

Function Signature

def productExceptSelf(nums: list[int]) -> list[int]:

Examples

Example 1: Input: nums = [1, 2, 3, 4] Output: [24, 12, 8, 6] Explanation: 234=24, 134=12, 124=8, 123=6.

Example 2: Input: nums = [-1, 1, 0, -3, 3] Output: [0, 0, 9, 0, 0] Explanation: When there is a zero, the product is 0 unless it is the index of the zero itself.

Edge Cases

  • Arrays containing one or more zeros.
  • Arrays with negative values.
  • Arrays of minimum length (2).

Hints

Hint 1

Think about the product of all elements to the left of index i and all elements to the right of index i separately.

Hint 2

Can you populate the output array by performing a forward pass to store prefix products, then a backward pass to multiply by suffix products?

Hint 3

Use a variable to keep track of the running suffix product during your second pass to maintain constant auxiliary space.

Follow-up questions

  • What happens if the input array contains multiple zeros? How does your logic handle that?
  • Can you generalize this to return an array where each index contains the product of elements at all indices except the current one, but only using O(1) space including the output array (e.g., if we were allowed to modify the output in place)?
  • How would you modify your solution if we were required to calculate the product of elements for a sliding window of size k instead?