1
\$\begingroup\$

Need help to optimize the following code for lower time complexity:

arrayMultiply(ipnArray: number[]): number[] {
  let outArray = [];
  for (let i=0; i<ipnArray.length; i++){
    let currentNum = ipnArray[i];
    let newArr = ipnArray.filter(nub => nub !== currentNum);
    let tempValue;
    for (let j=0; j<newArr.length; j++ ){
        if (tempValue) {
            tempValue = tempValue * newArr[j];
        
        }else{
            tempValue = newArr[j];
        }
    }
    outArray.push(tempValue);
  }
  return outArray;
}

This method takes an input of an array of numbers and returns the array where each element is a product of the other elements even if it has duplicate values. For Example: [1,2,3] becomes [6,3,2] Example 2: [1, 2, 2, 3] will be [12, 6, 6, 4]

Edit: My bad. the return should be [6, 3, 2] instead of the previous typo.

\$\endgroup\$
3
  • \$\begingroup\$ I'm sorry, but your script does not return [12, 6, 6, 4] for [1, 2, 2, 3]. \$\endgroup\$
    – RoToRa
    Sep 10, 2021 at 17:55
  • \$\begingroup\$ The filter function will filter out all instances of an array value. So if your array is [12,2,2,4], eventually filter will return the array [12,4]. Did you mean for this to happen? \$\endgroup\$
    – moonman239
    Sep 27, 2021 at 15:03
  • \$\begingroup\$ Admittedly, I'm not sure how to interpret this problem. \$\endgroup\$
    – moonman239
    Sep 27, 2021 at 15:57

3 Answers 3

4
\$\begingroup\$

That takes quadratic time. I'd say the intended/standard way is to compute prefix products and suffix products and for any number, multiply its prefix product with its suffix product. That's linear time. And unlike the divide-the-whole-product-by-the-number approach it doesn't have an issue with zeros or with the whole-array product being too large.

Example:

Input:           [2, 3, 5, 7]
Prefix products: [1, 2, 6, 30] (computed forwards)
Suffix products: [105, 35, 7, 1] (computed backwards)
Result:          [1*105, 2*35, 6*7, 30*1]
\$\endgroup\$
6
  • \$\begingroup\$ Hi. I've been doing this exact problem. Could you please explain how you would do this in TypeScript? \$\endgroup\$
    – moonman239
    Sep 27, 2021 at 14:52
  • \$\begingroup\$ @moonman239 I'd probably do it the same way. Is there something special about TypeScript? I'm not familiar with it. \$\endgroup\$
    – no comment
    Sep 27, 2021 at 15:34
  • \$\begingroup\$ I guess what I'm wondering is - what's a prefix product and suffix product, and how do you compute it? Are you saying that OP really can't improve the time complexity? \$\endgroup\$
    – moonman239
    Sep 27, 2021 at 15:56
  • \$\begingroup\$ @moonman239 Hmm? In my answer I say they can improve the time complexity (and how). Prefix product is the product of a prefix. See this for example. \$\endgroup\$
    – no comment
    Sep 27, 2021 at 16:00
  • \$\begingroup\$ OK. I think I'm doing something like that already: function replaceWithProduct(array: number[]) { for (let i=0; i<array.length; i++) { let arrayWithoutElement = array.slice(0,i).concat(array.slice(i+1,array.length)); array[i] = productOfArray(arrayWithoutElement); } return array; } \$\endgroup\$
    – moonman239
    Sep 27, 2021 at 16:09
1
\$\begingroup\$

The solution you proposed consisted of two nested loops: First loop iterates n time. Inside that, you have a filter and a second loop for all the elements except the currentNum, which is n - 1 time. Therefore time complexity is \$\mathcal{O}(n ( (n - 1)+n )) = \mathcal{O}(n^2)\$

If you want to iterate over all the elements in an array except for one, a better approach can be skipping the loop with continue when index counter is equal to that index.

An alternative solution for this problem can be based on the product of all numbers in the list. "Each element is the product of all the elements except itself", means by dividing each element from the total product you can eliminate the effect of current element in the product. This approach will be \$\mathcal{O}(n + n) = \mathcal{O}(n)\$: one iteration over all elements to get the product and another to calculate the values.

In case you want to return a new array with the results (just as what it states in the function signature), space complexity will be of \$\mathcal{O}(n)\$, but you can modify the same array, therefore \$\mathcal{O}(1)\$.

One special case for this scenario is zero: When the product of all elements in zero, return an array with the same length of input as zero. Note that it will only work for an array of non-zero elements.

This is what it would look like

function nonZeroArrayMultiply(list: number[]): number[] {
    const allProd = list.reduce((prod, cur) => prod * cur)
    let result = []
    for (let n of list)
        result.push(allProd / n)
    return result
}
\$\endgroup\$
5
  • \$\begingroup\$ How well does this approach work in the presence of zeros? \$\endgroup\$ Sep 10, 2021 at 9:51
  • \$\begingroup\$ @mdfst13 Thank you for your comment. This was the first type I was contributing here, and apparently my answer wasn't exactly the way it was expected to be. I completely edited my answer to comply with CodeReview community guidelines. \$\endgroup\$
    – Rsh
    Sep 10, 2021 at 16:05
  • \$\begingroup\$ @TobySpeight If the result of multiplication is zero, return an array with the same length filled with zeros. \$\endgroup\$
    – Rsh
    Sep 10, 2021 at 16:06
  • \$\begingroup\$ I don't see how this version does that; am I missing something?. If that is what it does (please explain what I'm missing), then it's wrong anyway (when exactly one input element is zero, then the corresponding output entry should be non-zero). \$\endgroup\$ Sep 21, 2021 at 7:38
  • \$\begingroup\$ @TobySpeight You're right, this does not work for arrays with zeros. We can consider the special case of zero with counting them (More than one zero, return array of zeros, if only one zero, return product of all for this index), but it won't be a pleasant solution. Other solutions do not have this issue. I will update the answer. Thanks. \$\endgroup\$
    – Rsh
    Sep 21, 2021 at 8:51
0
\$\begingroup\$

I haven't written JavaScript in years, so won't attempt a coded response.

If you ran your code and showed us the output, there wouldn't be typos, and it would show that you've actually tested your code.

Your solution unnecessarily creates temporary arrays, when it could simply omit the relevant cell from the calculation. That would speed things up a little.

(Note: I'm not sure your filter would work correctly with repeated values. If I understand it, it would change the results of your second example. Edit: I've checked and I'm fairly confident - your filter discards duplicated values, so your second example doesn't work.)

However, I think we can do this in two passes, provided the numbers are small enough that we won't hit arithmetic overflow (and that's a potential problem with any solution).

If P is the product of all values in ipnArray, then outArray[n] is P/ipnArray[n]. Two simple passes.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.