Given an array of numbers, returning an array of products of all other numbers without using division is a classic problem that tests both algorithmic reasoning and array manipulation skills. Below, we will explore a comprehensive approach to solving this problem, along with technical insights and examples.

Problem Explanation

The problem requires constructing an output array such that each element at index i is the product of all the numbers in the input array except the one at i. Crucially, you must not use division in your solution.

Example

Consider the input array: [1, 2, 3, 4]. The task is to produce an output array [24, 12, 8, 6], where:

• 24 is the product of 2, 3, and 4.
• 12 is the product of 1, 3, and 4.
• 8 is the product of 1, 2, and 4.
• 6 is the product of 1, 2, and 3.

Technical Approach

To solve this issue without using division, we can employ a method involving prefix and suffix products. This method efficiently calculates the desired products in two main passes through the array.

1. Prefix Products: First, we compute an array that contains the product of all elements preceding the current element. This operation is done in a single left-to-right traversal.
2. Suffix Products: Next, we compute an array for the products of all elements following the current element in a right-to-left traversal.
3. Combine Products: Finally, the product of all other numbers for a given index is simply the product of the corresponding prefix and suffix products.

Algorithm Steps

1. Initialize arrays prefix and suffix to 1, with the same length as the input array.
2. Populate the prefix array:
   • Start with prefix[0] = 1.
   • Iterate through the array from 1 to n-1, setting prefix[i] = prefix[i-1] * array[i-1].
3. Populate the suffix array:
   • Start with suffix[n-1] = 1.
   • Iterate from n-2 down to 0, setting suffix[i] = suffix[i+1] * array[i+1].
4. The result at each index i is prefix[i] * suffix[i].

Example Calculation

Let's walk through the calculation for arr = [1, 2, 3, 4]:

1. Prefix Calculation:
   • prefix[0] = 1
   • prefix[1] = prefix[0] * array[0] = 1 * 1 = 1
   • prefix[2] = prefix[1] * array[1] = 1 * 2 = 2
   • prefix[3] = prefix[2] * array[2] = 2 * 3 = 6 Resulting prefix Array: [1, 1, 2, 6]
2. Suffix Calculation:
   • suffix[3] = 1
   • suffix[2] = suffix[3] * array[3] = 1 * 4 = 4
   • suffix[1] = suffix[2] * array[2] = 4 * 3 = 12
   • suffix[0] = suffix[1] * array[1] = 12 * 2 = 24 Resulting suffix Array: [24, 12, 4, 1]
3. Final Product Calculation:
   • output[0] = prefix[0] * suffix[0] = 1 * 24 = 24
   • output[1] = prefix[1] * suffix[1] = 1 * 12 = 12
   • output[2] = prefix[2] * suffix[2] = 2 * 4 = 8
   • output[3] = prefix[3] * suffix[3] = 6 * 1 = 6 Resulting Output Array: [24, 12, 8, 6]

Complexity Analysis

• Time Complexity: The algorithm runs in $O(n)$ time, where n is the length of the input array. This is because each of the three major steps (building prefix, building suffix, computing the final result) involves a single pass through the array.
• Space Complexity: The algorithm uses $O(n)$ additional space for the prefix and suffix arrays. The space for the output array does not count towards extra space because it is returned as part of the solution.

Key Points Summary

Considerations and Alternative Approaches

• Edge Cases: Consider handling arrays containing one element or zeros, which might require additional checks.
• Improving Space Complexity: You can optimize space usage to $O(1)$ by directly modifying the output array for prefix values, then iterating backward for suffix computations.

This approach ensures that we efficiently compute the required products without any reliance on division, making the solution applicable to scenarios where division is not suitable due to potential division by zero concerns or when optimizing for integer arithmetic.