Constant space restriction on an array SDE interview questions. A doubts for a classic interview questions

Question

You are given an array [a1 To an] and we have to construct another array [b1 To bn] where bi = a1*a2*…*an/ai. you are allowed to use only constant space and the time complexity is O(n). No divisions are allowed.

The logic of solution is quite simple, remove the bi from the product to get the result. However, when I processed to solve this problem I found myself be trapped. Here is my doubts:

According to my understanding, the constant space here means despite the length of the array, the number of variables I can use have to be fixed. Which forbids to create a new arrays to solve the problem. Because creating new arrays makes the number of variables different when dealing with different arrays.

I have searched most solution for this online, however all the solutions I can find created new arrays. So, did I miss anything here? Any thoughts? Thank you very much!

Answer 1

I'm going to use array indices from 0 to N-1 because that's how we do things in the hood.

You can rewrite the equation for b_i like this: b_i = (a₀×a₁×⋯×a_i-1) × (a_i+1×a_i+2×⋯×a_n-1), or more succinctly like this: b_i = (∏_j=0⋯i-1 a_j) × (∏_j=i+1⋯n-1 a_j).

(In case you're not familiar with it, ∏ is like ∑ but it multiplies the terms instead of adding them. Also, these formulas are not quite the same as the formula in your question, because according to the formula in your question, b_i is undefined if a_i is zero. However, I will assume that the intent is to cancel the a_i in the numerator and denominator, even if it is zero.)

Anyway, you can compute the left subproducts (∏_j=0⋯i-1 a_j) incrementally by traversing array a from 0 to n-1. You can compute the right subproducts (∏_j=i+1⋯n-1 a_j) by traversing the array a from n-1 to 0.

Thus the solution is to use two passes.

The first pass is from 0 to N-1. Set each b[i] to the product of a[j] for 0 <= j < i. This pass sets the b array to the left subproducts. This takes O(N) time and constant space for the loop counter.

The second pass is from N-1 to 0. Update each b[i] by multiplying it by the product of a[j] for i < j < N. Thus pass updates the b array by multiplying each element by the appropriate right subproduct. This takes O(N) time and constant space for the loop counter and a temporary.

Here's a Python solution:

b[0] = 1
for i in range(1, N):
    b[i] = b[i - 1] * a[i - 1]

# Now every b[i] is the product of the a[j] where 0 <= j < i.

t = 1
for i in range(N-1, -1, -1):
    b[i] = b[i] * t
    t *= a[i]

# Now every b[i] is the product of the a[j] where 0 <= j < i
# and the a[j] where i < j <= N-1.  This is the desired output.

Answer 2

A constant space requirement doesn't forbid the creation of new arrays. It just means that your algorithm needs to use the same amount of space each time it runs. Since the question asks you to construct a new array, I'm going to show a function that does this with constant space and in linear time.

You can still create a new array. Just make sure that it's a constant size. The easiest way to do this is to make it the largest possible size. For example, in C++ you could use

int* b  = new int[UINT_MAX];

since the largest index that be used in array is UINT_MAX. Here is a solution that is both linear time, constant space, and constructs a new array as desired.

int* prod(int *a, int len) {
    int* b  = new int[UINT_MAX];
    int tmp = 1;
    b[0] = 1;
    for (int i = 1; i < len; i += 1) b[i] = b[i - 1] * a[i - 1];
    for (int i = len - 1; i >= 0; i -= 1) {
        b[i] = b[i] * tmp;
        tmp *= a[i];
    } // for
    return b;
} // prod

The contract of the function should be that the size of the new array is the same as the input array (even though we secretly know it's bigger). This, of course, is not as efficient as calculating it in-place, but that's NOT what the question is asking (at least the way that it's worded).