How to Solve: Product of Array Except Self

How to Solve: Product of Array Except Self

(Complete Guide for FAANG-Level Interviews)

? Introduction

"This problem appears in 1 out of every 3 onsite interviews—master it, and you’ll prove you can optimize space, handle edge cases, and think in O(n) time—exactly what FAANG interviewers want to see."

? WHAT YOU NEED TO KNOW FIRST

Before tackling this problem, you must understand: 1. Prefix & Suffix Products – How to compute running products from left and right. 2. Space-Time Tradeoffs – When to use extra space vs. in-place computation. 3. Edge Cases in Arrays – Handling zeros, single-element arrays, and duplicates.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

(Repeatable mental checklist for every "Product Except Self" problem.)

1. Clarify Constraints
2. Can I use division? (Usually no.)
3. Can I modify the input array? (Usually yes, but confirm.)

4. What’s the expected time/space complexity? (O(n) time, O(1) extra space.)

5. Handle Edge Cases

6. Empty array → Return [].
7. Single-element array → Return [1] (or [0] if input is [0]).
8. Array with one zero → All outputs are zero except at the zero’s index.

9. Array with two+ zeros → All outputs are zero.

10. Initialize Output Array

11. Create an array result of the same length as nums, initialized to 1.

12. First Pass (Left Products)

13. Traverse left to right.

14. For each i, set result[i] = result[i-1] nums[i-1] (prefix product).

15. Second Pass (Right Products)

16. Traverse right to left.
17. Maintain a running product right_product.
18. For each i, update result[i] = right_product.

19. Update right_product = nums[i].

20. Return Result

21. The result array now contains products except self.

22. Verify with Examples

23. Test with [1,2,3,4], [0,1,2], [1,0,3,0].

? WORKED EXAMPLES

Example 1 – Basic (No Zeros)

Problem: Given nums = [1,2,3,4], return [24,12,8,6].

Step-by-Step: 1. Edge Case: Not empty, no zeros → proceed. 2. Initialize result = [1,1,1,1]. 3. First Pass (Left Products):
- i=0: result[0] = 1 (no left elements).
- i=1: result[1] = result[0] nums[0] = 1 1 = 1.
- i=2: result[2] = result[1] nums[1] = 1 2 = 2.
- i=3: result[3] = result[2] nums[2] = 2 3 = 6.
- result = [1,1,2,6]. 4. Second Pass (Right Products):
- right_product = 1.
- i=3: result[3] = right_product → 6 1 = 6.
right_product = nums[3] → 1 4 = 4.
- i=2: result[2] = right_product → 2 4 = 8.
right_product = nums[2] → 4 3 = 12.
- i=1: result[1] = right_product → 1 12 = 12.
right_product = nums[1] → 12 2 = 24.
- i=0: result[0] = right_product → 1 24 = 24. 5. Final result = [24,12,8,6].

Code (Python):

def productExceptSelf(nums):

    n = len(nums)

    result = [1]  n


    # Left pass

    for i in range(1, n):

        result[i] = result[i-1]  nums[i-1]


    # Right pass

    right_product = 1

    for i in range(n-1, -1, -1):

        result[i] = right_product

        right_product = nums[i]


    return result

Time Complexity: O(n) (two passes). Space Complexity: O(1) extra space (output array doesn’t count).

Why This Works: - The left pass computes products of all elements to the left of i. - The right pass multiplies these with products of all elements to the right of i. - No division → handles zeros gracefully.

Example 2 – Medium (One Zero)

Problem: Given nums = [0,1,2], return [2,0,0].

Step-by-Step: 1. Edge Case: One zero → all outputs are zero except at the zero’s index. 2. Initialize result = [1,1,1]. 3. First Pass (Left Products):
- i=0: result[0] = 1.
- i=1: result[1] = result[0] nums[0] = 1 0 = 0.
- i=2: result[2] = result[1] nums[1] = 0 1 = 0.
- result = [1,0,0]. 4. Second Pass (Right Products):
- right_product = 1.
- i=2: result[2] = right_product → 0 1 = 0.
right_product = nums[2] → 1 2 = 2.
- i=1: result[1] = right_product → 0 2 = 0.
right_product = nums[1] → 2 1 = 2.
- i=0: result[0] = right_product → 1 2 = 2. 5. Final result = [2,0,0].

Code: Same as above (handles zeros automatically).

Why This Works: - The left pass sets result[i] to 0 if there’s a zero to the left. - The right pass multiplies by the product of elements to the right, but zeros propagate.

Example 3 – Hard (Two Zeros)

Problem: Given nums = [1,0,3,0], return [0,0,0,0].

Step-by-Step: 1. Edge Case: Two zeros → all outputs are zero. 2. Initialize result = [1,1,1,1]. 3. First Pass (Left Products):
- i=0: result[0] = 1.
- i=1: result[1] = result[0] nums[0] = 1 1 = 1.
- i=2: result[2] = result[1] nums[1] = 1 0 = 0.
- i=3: result[3] = result[2] nums[2] = 0 3 = 0.
- result = [1,1,0,0]. 4. Second Pass (Right Products):
- right_product = 1.
- i=3: result[3] = right_product → 0 1 = 0.
right_product = nums[3] → 1 0 = 0.
- i=2: result[2] = right_product → 0 0 = 0.
right_product = nums[2] → 0 3 = 0.
- i=1: result[1] = right_product → 1 0 = 0.
right_product = nums[1] → 0 0 = 0.
- i=0: result[0] = right_product → 1 0 = 0. 5. Final result = [0,0,0,0].

Why This Works: - The second zero ensures right_product becomes 0, zeroing out all results.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap (Closing Script)

"Here’s the playbook for ‘Product of Array Except Self’: 1. Clarify constraints—can you use division? Usually no. 2. Handle edge cases—empty array, single element, zeros. 3. Two-pass approach—left products first, then right products. 4. Optimize space—use the output array to store prefix products. 5. Test with zeros—one zero? All outputs zero except at its index. Two zeros? All outputs zero.

This pattern shows up in interviews because it tests your ability to optimize space and handle edge cases. Practice it until you can code it in under 10 minutes—then you’ll walk into your interview with confidence."

? Final Notes

• Practice Variations: Try with negative numbers, large arrays, or follow-ups like "Can you do it in one pass?"
• Whiteboard First: Sketch the two-pass approach before coding.
• Time Yourself: Aim for <10 minutes from problem statement to working code.

This guide is 100% interview-ready—use it to dominate your next FAANG interview! ?