Product of Array except self

Problem

Let’s take a look at the question,

Group Anagrams

Given an array of strings strs, group the together. You can return the answer in any order.

Input: strs = ["eat","tea","tan","ate","nat","bat"]

Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Click on the above card to go to the problem on LeetCode.

Approach

My first approach was pretty bad, so go easy on yourself. This is a medium level problem.

note that we are not gonna use division.

We are going to create two lists that are the product of the elements in nums from left to right and right to left.

I know what you’re thinking, multiply however you want but the product will be the same!

refer this great video by greg for a much deeper understanding

Solution

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        left , right = 1, 1
        n = len(nums)
        left_arr = [0] * n
        right_arr = [0] * n


        for i in range(n):
            j = -i -1
            left_arr[i] = left
            right_arr[j] = right
            left *= nums[i]
            right *= nums[j]

        
        return [l*r for l, r in zip(left_arr, right_arr)]