DSA-005 · FOCUSED PRACTICE
Product of Array Except Self
Intermediate · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 19535 deterministic checks. Learner drafts are not executed.
Understand the problem
Return an array whose entry i is the product of all input values except nums[i]. Do not use division, and preserve the input.
- nums is non-null with 0–100,000 signed int values. The product of the absolute magnitudes of all nonzero elements is guaranteed to be at most Long.MAX_VALUE (empty nonzero product is 1). This guarantees every product used here fits long.
- Return a new long[] of equal length. Empty input returns []; a singleton returns [1], because the product of no factors is 1.
- Zeros and negative values are allowed. Preserve nums. The optimized method uses O(1) auxiliary scalars excluding the required output array. Inputs violating the numeric guarantee are outside this contract.
Examples
Input:
[1,2,3,4]
Output:[24,12,8,6]Each entry combines factors strictly to its left and right.
Input:
[-1,1,0,-3,3]
Output:[0,0,9,0,0]Only the zero’s position excludes the unique zero; its remaining product is 9.
Input:
[0,0,2]
Output:[0,0,0]Every excluded-position product still contains a zero.
Before you start
- Empty-product identity and two directional scans
- Explicit numeric bounds and zero behavior
Recognize the structure
The output at an index combines two disjoint regions: all values before it and all after it. Reusing prefix/suffix products removes repeated multiplication and naturally handles zeros. This is not a division problem disguised as an array loop.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 114/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
Try before revealing
Hint 1
Separate the factors before i from the factors after i.
Hint 2
Store the left product without including nums[i].
Hint 3
Multiply those stored prefixes by a running exclusive suffix in a backward pass.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Multiply every other position separately
For each i, start product=1 and multiply every nums[j] with j≠i. On [2,3,4], this computes 3×4, 2×4, and 2×3 independently. The method is O(n²) time and uses O(1) scalars beyond O(n) output. It is simple and provides a small-input reference, but repeats nearly all factors.
Improve the baseline
Write exclusive prefixes into output
Before index i, prefix equals the product of nums[0..i). Store that value in answer[i], then multiply nums[i] into prefix.
Sweep exclusive suffixes backward
Before visiting i from the right, suffix equals the product strictly after i. Multiply answer[i] by suffix before including nums[i] in suffix.
Reuse the required output storage
A separate prefix and suffix array would be correct but unnecessary. Prefix entries can live in answer, and one running suffix supplies the other half. Zeros require no special branch.
Why it is correct
Prefix invariant
Initialize prefix=1, the empty product. Storing it before multiplication gives precisely the factors strictly left of i; the update establishes the next prefix.
Suffix invariant
Initialize suffix=1 at the right boundary. Before the backward update at i, answer[i] contains its exclusive prefix and suffix contains its exclusive suffix. Their product uses every input factor except i exactly once.
Completion
After the backward pass, every output entry is complete. Both scans terminate after at most n iterations. Empty and singleton arrays follow the same identity conventions, and the numeric guarantee bounds every intermediate product.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
public final class Solution {
public static long[] productExceptSelf(int[] nums) {
long[] answer = new long[nums.length];
long prefix = 1;
for (int i = 0; i < nums.length; i++) {
answer[i] = prefix;
prefix *= nums[i];
}
long suffix = 1;
for (int i = nums.length - 1; i >= 0; i--) {
answer[i] *= suffix;
suffix *= nums[i];
}
return answer;
}
public static long[] baseline(int[] nums) {
long[] answer = new long[nums.length];
for (int i = 0; i < nums.length; i++) {
long product = 1;
for (int j = 0; j < nums.length; j++) if (j != i) product *= nums[j];
answer[i] = product;
}
return answer;
}
}
Read the meaningful blocks
Use long output and accumulators
Products can exceed int even when every input fits int.
Store before including the current factor
Including nums[i] too early would violate the except-self requirement.
Exclude output from auxiliary accounting explicitly
O(1) extra scalars does not mean the returned n-element array consumes no memory.
Complexity
O(n) time using fixed-width long multiplication, O(1) auxiliary scalar space, and O(n) separately counted output storage. Input is preserved.
The direct baseline is O(n²) time with the same output/scalar storage. Without a fixed numeric bound or with BigInteger, arithmetic cost depends on product bit length; this lesson does not silently assume arbitrary-precision multiplication is constant time.
Exact-state walkthroughs
Reveal normal and boundary traces
Two exclusive directional products
Input: [1,2,3,4] · Result: [24,12,8,6]
Step 1 of 10: Initialize an output buffer and the empty-product identity.
No current input factor has been included in its own output.
- 0: 0
- 1: 0
- 2: 0
- 3: 0
| Variable | Value |
|---|---|
| answer | [0,0,0,0] |
| prefix | 1 |
See the affected Java block
1 public final class Solution { 2 public static long[] productExceptSelf(int[] nums) { 3 long[] answer = new long[nums.length]; 4 long prefix = 1; 5 for (int i = 0; i < nums.length; i++) { 6 answer[i] = prefix; 7 prefix *= nums[i]; 8 } 9 long suffix = 1; 10 for (int i = nums.length - 1; i >= 0; i--) { 11 answer[i] *= suffix; 12 suffix *= nums[i]; 13 } 14 return answer; 15 } 16 public static long[] baseline(int[] nums) { 17 long[] answer = new long[nums.length]; 18 for (int i = 0; i < nums.length; i++) { 19 long product = 1; 20 for (int j = 0; j < nums.length; j++) if (j != i) product *= nums[j]; 21 answer[i] = product; 22 } 23 return answer; 24 } 25 } 26
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Initialize an output buffer and the empty-product identity.
No current input factor has been included in its own output.
- answer
[0,0,0,0]- prefix
1
- Write the exclusive prefix, then include this factor for the next index.
answer[0..i] holds products strictly before each index; prefix now covers 0..i.
- i
0- answer
[1,0,0,0]- prefix
1
- Write the exclusive prefix, then include this factor for the next index.
answer[0..i] holds products strictly before each index; prefix now covers 0..i.
- i
1- answer
[1,1,0,0]- prefix
2
- Write the exclusive prefix, then include this factor for the next index.
answer[0..i] holds products strictly before each index; prefix now covers 0..i.
- i
2- answer
[1,1,2,0]- prefix
6
- Write the exclusive prefix, then include this factor for the next index.
answer[0..i] holds products strictly before each index; prefix now covers 0..i.
- i
3- answer
[1,1,2,6]- prefix
24
- Combine the exclusive suffix, then advance the running suffix.
Outputs from i through the end are final; every other entry is still a prefix product.
- i
3- answer
[1,1,2,6]- suffix
4- completeFrom
3
- Combine the exclusive suffix, then advance the running suffix.
Outputs from i through the end are final; every other entry is still a prefix product.
- i
2- answer
[1,1,8,6]- suffix
12- completeFrom
2
- Combine the exclusive suffix, then advance the running suffix.
Outputs from i through the end are final; every other entry is still a prefix product.
- i
1- answer
[1,12,8,6]- suffix
24- completeFrom
1
- Combine the exclusive suffix, then advance the running suffix.
Outputs from i through the end are final; every other entry is still a prefix product.
- i
0- answer
[24,12,8,6]- suffix
24- completeFrom
0
- Return the contract result.
The completed state satisfies the declared output and mutation contract.
- result
[24,12,8,6]
A single zero
Input: [0,2,3] · Result: [6,0,0]
Step 1 of 8: Initialize an output buffer and the empty-product identity.
No current input factor has been included in its own output.
- 0: 0
- 1: 0
- 2: 0
| Variable | Value |
|---|---|
| answer | [0,0,0] |
| prefix | 1 |
See the affected Java block
1 public final class Solution { 2 public static long[] productExceptSelf(int[] nums) { 3 long[] answer = new long[nums.length]; 4 long prefix = 1; 5 for (int i = 0; i < nums.length; i++) { 6 answer[i] = prefix; 7 prefix *= nums[i]; 8 } 9 long suffix = 1; 10 for (int i = nums.length - 1; i >= 0; i--) { 11 answer[i] *= suffix; 12 suffix *= nums[i]; 13 } 14 return answer; 15 } 16 public static long[] baseline(int[] nums) { 17 long[] answer = new long[nums.length]; 18 for (int i = 0; i < nums.length; i++) { 19 long product = 1; 20 for (int j = 0; j < nums.length; j++) if (j != i) product *= nums[j]; 21 answer[i] = product; 22 } 23 return answer; 24 } 25 } 26
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Initialize an output buffer and the empty-product identity.
No current input factor has been included in its own output.
- answer
[0,0,0]- prefix
1
- Write the exclusive prefix, then include this factor for the next index.
answer[0..i] holds products strictly before each index; prefix now covers 0..i.
- i
0- answer
[1,0,0]- prefix
0
- Write the exclusive prefix, then include this factor for the next index.
answer[0..i] holds products strictly before each index; prefix now covers 0..i.
- i
1- answer
[1,0,0]- prefix
0
- Write the exclusive prefix, then include this factor for the next index.
answer[0..i] holds products strictly before each index; prefix now covers 0..i.
- i
2- answer
[1,0,0]- prefix
0
- Combine the exclusive suffix, then advance the running suffix.
Outputs from i through the end are final; every other entry is still a prefix product.
- i
2- answer
[1,0,0]- suffix
3- completeFrom
2
- Combine the exclusive suffix, then advance the running suffix.
Outputs from i through the end are final; every other entry is still a prefix product.
- i
1- answer
[1,0,0]- suffix
6- completeFrom
1
- Combine the exclusive suffix, then advance the running suffix.
Outputs from i through the end are final; every other entry is still a prefix product.
- i
0- answer
[6,0,0]- suffix
0- completeFrom
0
- Return the contract result.
The completed state satisfies the declared output and mutation contract.
- result
[6,0,0]
Test the contract
Input:
[]
Output:[]No output positions.
Input:
[7]
Output:[1]Empty product identity.
Input:
[0,2,3]
Output:[6,0,0]One zero.
Input:
[-2,3,-4]
Output:[-12,8,-6]Sign handling.
Common mistakes and counterexamples
Divide total product by the current element
Counterexample: [0,2,3] needs [6,0,0] and division by zero is undefined.
Use exclusive prefix and suffix products.
Include the current factor in both scans
Counterexample: [2,3] needs [3,2], not the total at each position.
Store or combine before updating the running product.
Initialize accumulators to zero
Counterexample: [2,3] would incorrectly produce all zeros.
The multiplicative identity is one.
Ignore overflow guarantees
Counterexample: Large unconstrained products do not fit long.
State bounds, use checked arithmetic, or derive BigInteger costs under a changed contract.
Follow-ups
Division is allowed.
Count zeros first. With no zeros, division may work under exact arithmetic; with one zero, only its position can be nonzero; with multiple zeros, every result is zero. Overflow still needs an explicit policy.
Support arbitrary-size products.
Use BigInteger and account for growing bit lengths and stored output size. Two linear scans in element count do not imply linear bit-operation cost.
Answer many range-product queries with updates.
A single prefix product cannot generally be divided safely around zeros. Consider a segment tree whose nodes retain enough product/zero information for the chosen arithmetic model.