Problems/Prefix Sums/Product Array Without Current Element
Prefix Sums
medium

Product Array Without Current Element

The 'Modified Product Array' problem challenges you to create a new array where each element is the product of all other numbers in the input array, excluding the number at that index. This tests your ability to manipulate arrays efficiently and think creatively about prefix and suffix products.

arrayprefix-sumproductoptimizationinterview-question

Problem Statement

Given an array of integers, construct a new array where each element at index 'i' is equal to the product of all the integers in the original array, except for the integer at index 'i'. You are not allowed to use division in your solution.

Example 1
Input: [1, 2, 3, 4]
Output: [24, 12, 8, 6]
The output array is calculated as follows: output[0] = 2 3 4 = 24, output[1] = 1 3 4 = 12, output[2] = 1 2 4 = 8, output[3] = 1 2 3 = 6.
Example 2
Input: [5, 1, 0, 2]
Output: [0, 0, 10, 0]
The output array is calculated as follows: output[0] = 1 0 2 = 0, output[1] = 5 0 2 = 0, output[2] = 5 1 2 = 10, output[3] = 5 1 0 = 0.
Constraints
  • -The length of the input array will be greater than 1.
  • -The elements of the array can be positive, negative, or zero.
  • -You must solve the problem without using division.
  • -The product of any prefix or suffix of the array will fit within a 32-bit integer.

Brute Force Approach

The brute force approach is like calculating the total score for a bowling team, but you have to recalculate the entire score for each bowler, leaving out their individual score each time. You'd iterate through the array, and for each index, iterate through the rest of the array to compute the product, skipping the current index. This results in redundant calculations.

TimeO(n^2)
SpaceO(1)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem