AI Hints
Home›DSA in Python Tutorial›Array Interview Problems
DSA in Python · Lesson 107 of 132

Practice: Product Except Self

Left and right passes.

⏱ 2 min read▶ Video at 2:08:04🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

For each number in a list, find the product of all the other numbers. The catch is, you're not allowed to divide. Pause. How could you get everything to the left, and everything to the right?

Practice: Product Except Self
From the video: Practice: Product Except Self
  • Product of all the others
  • No division allowed
  • Left and right?

Two sweeps

In the first sweep, going left to right, each position gets the product of everything before it. In the second sweep, going right to left, we multiply in the product of everything after it. Together, that's everything except the number itself. Run it. For one, two, three, four, the answers are twenty four, twelve, eight, and six.

product.pypython
def product_except_self(nums):
    n = len(nums)
    out = [1] * n
    left = 1
    for i in range(n):
        out[i] = left
        left *= nums[i]
    right = 1
    for i in range(n - 1, -1, -1):
        out[i] *= right
        right *= nums[i]
    return out

print(product_except_self([1, 2, 3, 4]))
Output
[24, 12, 8, 6]

The prefix idea, again

This is the prefix sum idea, using products. The left sweep is a prefix product, and the right sweep is a suffix product. Many array problems become easy when you precompute what's to the left, and what's to the right, of every position.

keyvalue
Left sweepproduct before i
Right sweepproduct after i
Combinemultiply them
CostO(n), no division

Summary

A left sweep and a right sweep give the product of everything else, without division, in O of N. Next, trapping rain water.

Key takeaways
  • Prefix products
  • Suffix products
  • Multiply them
Next up: Practice: Trapping Rain Water — water between the walls