Instantly share code, notes, and snippets.

toritsejuFO/algorithm_fridays_week04.py

Last active May 2, 2021 17:39
Star You must be signed in to star a gist
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 from functools import reduce def get_products(nums): products = [] if nums == None or len(nums) == 0 or len(nums) == 1: return products for i, el in enumerate(nums): nums_to_multiply = nums[:i] + nums[i+1:] product = reduce(lambda x, y: x * y, nums_to_multiply) products.append(product) return products if __name__ == '__main__': nums = [4, 5, 10, 2] products = get_products(nums) print(products)

meekg33k commented May 2, 2021 • edited

Very neat and robust solution @toritsejuFO and thank you for participating in Week 4 of Algorithm Fridays.

I like your use of a lambda function, and your handling of edge cases - invalid or null input, real clean!

What do you think the time complexity of your solution is, because you are looping over the input array on line 9, and in that loop you are using a `reduce` function. That seems like a nested loop right there.

The other thing I'd say is, what's your reason for creating a new array on line 5? How do you think that affects memory efficiency?

But in all, a real clean solution!

toritsejuFO commented May 2, 2021

Thanks a lot for your feedback @meekg33k.

Yeah, it's equivalent to a nested loop, because reduce takes about O(n) since it iterates through all the elements, even though it's n-1 elements in this case, that's still ~n. And then I'm also iterating through each element as well. So time complexity is O(n^2), because for each element I go through in my iteration, reduce goes through all other elements.

I initially thought I could do it without having to create a new array, but I would be modifying the existing one, making it impossible to get the subsequent products as I proceed. So I had to create a new array to hold each product to avoid mutation of the original. This implies double the memory space, so not very memory efficient if we consider that `nums` is a very large array. I'm already excited to see your incoming solution and how you handle this.

Also, I store the other elements to be multiplied in a temporary array as well during my iteration (I could have passed directly to reduce, but it wouldn't be easily readable), but each iteration does away the space every time, so that was acceptable to me.

Thanks again, I really appreciate.