Answer: Expedia OA Question 2024 September | Arrays | on-campus

Solution: Product of Array Except Self — Prefix and Suffix Products Approach We cannot use division and must achieve O(N) time. The key insight is that answer[i] = (product of all elements to the LEFT of i) * (product of all elements to the RIGHT of i). First Pass (Left to Right): Build a prefix product array where answer[i] stores the product of all elements before index i. Second Pass (Right to Left): Multiply each answer[i] by the running suffix ...