How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Compute product excluding index without division

Quick Overview

This question evaluates array-manipulation and algorithmic problem-solving skills, focusing on computing a product-for-each-index using prefix and postfix accumulation concepts while reasoning about edge cases such as zeros, negative numbers, and integer overflow.

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Given an integer array nums, return an array ans where ans[i] equals the product of all elements of nums except nums[i], without using division. Achieve O(n) time and O( 1) extra space beyond the output array. Perform a step-by-step dry run showing how prefix and postfix accumulators update at each index. Explain how your solution handles zeros and negative numbers and how you would mitigate overflow in languages with fixed-width integers.

Quick Answer: This question evaluates array-manipulation and algorithmic problem-solving skills, focusing on computing a product-for-each-index using prefix and postfix accumulation concepts while reasoning about edge cases such as zeros, negative numbers, and integer overflow.

Given an integer array `nums`, return an array `ans` where `ans[i]` equals the product of every element of `nums` except `nums[i]`. You may NOT use the division operator. Solve it in O(n) time and O(1) extra space, not counting the output array itself. **Approach (prefix/postfix accumulators):** 1. First left-to-right pass: `ans[i]` holds the product of all elements strictly to the left of `i` (a running `prefix`, starting at 1). 2. Second right-to-left pass: multiply `ans[i]` by a running `postfix` of all elements strictly to the right of `i` (starting at 1). 3. After both passes `ans[i] = prefix(i) * postfix(i)` = product of everything except `nums[i]`. **Dry run on `[1,2,3,4]`** — prefix pass: ans=[1,1,2,6] (prefix updates 1→1→2→6→24). Postfix pass (right to left): i=3 ans[3]*=1→6, postfix=4; i=2 ans[2]*=4→8, postfix=12; i=1 ans[1]*=12→12, postfix=24; i=0 ans[0]*=24→24, postfix=24. Result `[24,12,8,6]`. **Zeros:** With one zero, only that index gets the product of the others; all other indices become 0. With two or more zeros, every output is 0 — the prefix/postfix method handles this automatically because the zero zeroes out every accumulator that crosses it. **Negatives:** sign is preserved naturally by multiplication; no special handling needed. **Overflow:** in fixed-width-integer languages the full product can exceed the type range; the problem guarantees the answer fits in 32-bit, but use a 64-bit accumulator (long / int64) for the intermediate prefix/postfix to stay safe.

Constraints

2 <= nums.length <= 10^5
-30 <= nums[i] <= 30
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer
You must NOT use the division operator
O(n) time; O(1) extra space not counting the output array

Examples

Input: ([1, 2, 3, 4],)

Expected Output: [24, 12, 8, 6]

Explanation: ans[0]=2*3*4=24, ans[1]=1*3*4=12, ans[2]=1*2*4=8, ans[3]=1*2*3=6.

Input: ([-1, 1, 0, -3, 3],)

Expected Output: [0, 0, 9, 0, 0]

Explanation: Exactly one zero (at index 2): every other index includes that zero in its product and becomes 0; index 2 gets (-1)*1*(-3)*3 = 9.

Input: ([2, 3],)

Expected Output: [3, 2]

Explanation: Two-element array: ans[0] is the other element (3), ans[1] is the other element (2).

Input: ([5],)

Expected Output: [1]

Explanation: Single element boundary: there are no other elements, so the empty product is 1.

Input: ([0, 0, 4],)

Expected Output: [0, 0, 0]

Explanation: Two or more zeros: every output index still has at least one zero factor, so all entries are 0.

Input: ([-2, -3, -4],)

Expected Output: [12, 8, 6]

Explanation: All negatives: signs combine by multiplication. ans[0]=(-3)*(-4)=12, ans[1]=(-2)*(-4)=8, ans[2]=(-2)*(-3)=6.

Hints

ans[i] = (product of everything to the LEFT of i) * (product of everything to the RIGHT of i). Compute each side with a single linear pass.
Reuse the output array as scratch: first store the left/prefix products, then multiply in the right/postfix products on a second pass — that keeps extra space O(1).
Carry one running accumulator per direction, initialized to 1. Multiply it by nums[i] AFTER writing it into ans[i] so the current element is excluded. Use a 64-bit accumulator to avoid intermediate overflow.

Quick Overview