Time complexity: O(n)

Space: constant (except the output array).

```
class Solution {
public int[] productExceptSelf(int[] nums) {
int[] output = new int[nums.length];
# First pass. Calculate a rolling product forward and save to output.
int product=1;
for (int i = 0; i < nums.length; i++) {
output[i] = product;
product *= nums[i];
}
# Second pass. Calcuate a rolling product backward and combine with
# the result from first pass.
product = 1;
for (int i = nums.length -1; i >= 0; i--) {
output[i] *= product;
product *= nums[i];
}
return output;
}
}
```