Array of Array Products
There is an array 'arr' of Integers of size n, for every index i (from 0 to n) you can calculate product of all element integers except that element.
Solve without using division and analyze your solution’s time and space complexities.
Examples:
input: arr = [8, 10, 2]
output: [20, 16, 80] # by calculating: [10*2, 8*2, 8*10]
input: arr = [2, 7, 3, 4]
output: [84, 24, 56, 42] # by calculating: [7*3*4, 2*3*4, 2*7*4, 2*7*3]
Top comments (7)
Swift Solution:
Output:
In the spirit of the last solution: for loops!
Your solution is O(n2) time complexity. You should try for more optimized solution.
After posting my first solution, I took a look at yours, and now I can't unsee it. So I took some time trying to come up with another creative solution, but in the end, I couldn't figure out anything that was more efficient than what you had posted.
I ran everything I tried through a little repetitive test to see how different approaches stacked up, so here's a quick rundown.
Basic test setup:
There is definitely a little overhead, but since they all ran through the same setup, I figured at least relatively speaking, the results should still be informative.
And here are the different functions tested:
I also noticed that over the course of 5mil(*3) runs, the overhead difference of creating an empty array and filling it vs initializing an array already of the full size you're going to use is pretty huge. ie:
test1() dropped from 8.5 sec to about 5.9 sec once I made that small change.
So between that and the revelation about how slow .filter() and .reduce() are in swift, Id say if you're serious about performance, it's going to be super important to really understand what's going on behind the scenes of all these standard libraries we take for granted.
Clojure solution
Note: This solution is O(n) because
(apply * list)
expands into(* list0 list1 ... listn)
java Sol :
you could optimize this solution for O(n)
hello,
i am new but it is O(n) right ? without the last loop ofc