Product Array - Interview Question

Friday, December 17, 2010 by gradbot

Given an array of numbers return an array where each item is replaced by the product of all the other items in the array.

A trivial solution would be to multiply the elements repeatedly for each result giving an O(n^2) solution.

var productOfOthers = function(input) {
    var length = input.length;
    
    var result = [];
    for (var i = 0; i < length; i++) {
        result[i] = 1;
        for (var j = 0; j < length; j++) {
            if (i != j) {
                result[i] *= input[j];
            }
        }
    }
    return result;
};

You could get the total product first and then divide by each element for O(n) but you may introduce floating point error and you have to deal with dividing by zero.

var productOfOthers = function(input) {
    var length = input.length;
    
    var product = 1;
    for (var i = 0; i < length; i++) {
        product *= input[i];
    }
    
    var result = [];
    for (var i = 0; i < length; i++) {
        result[i] = product / input[i];
    }
    
    return result;
};

Taking advantage of Multiplications Associative property you can get minimal error in O(n) by making two runners, one forward and one backward, to calculate the result by result[i] = forward[i-1] * backward[i+1].

var productOfOthers = function(input) {
    var length = input.length;
    
    if (length <= 1) {
        if (length == 1) {
            return [input[0]];
        } else {
            return [];          
        }
    }
        
    var forward = [];
    var product = 1;
    for (var i = 0; i < length; i++) {
        product *= input[i];
        forward[i] = product;
    }

    var backward = [];
    var product = 1;
    for (var i = length - 1; i >= 0; i--) {
        product *= input[i];
        backward[i] = product;
    }
    
    var result = [];
    for (var i = 1; i < length - 1; i++) {
        result[i] = forward[i - 1] * backward[i + 1];
    }

    result[0] = backward[1];
    result[length - 1] = forward[length - 2];   
    
    return result;
};

0 comments: