Compute Products Excluding Each Index
Company: Asana
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given an integer array `nums` of length `n`. Return an array `answer` such that `answer[i]` equals the product of every element of `nums` except `nums[i]`.
Requirements:
- Do not use division.
- Run in O(n) time.
- Use O(1) extra space besides the returned array if possible.
- Correctly handle zeros and negative numbers.
Example: `nums = [1, 2, 3, 4]` returns `[24, 12, 8, 6]`.
Follow-up: explain how your approach behaves when the input contains one zero or multiple zeros.
Quick Answer: This question evaluates array manipulation skills, arithmetic reasoning with cumulative products, edge-case handling for zeros and negative numbers, and time/space complexity optimization for in-place or constant-extra-space algorithms.
You are given an integer array `nums` of length `n`. Return an array `answer` such that `answer[i]` is equal to the product of every element in `nums` except `nums[i]`.
Requirements:
- Do not use division.
- Your algorithm must run in O(n) time.
- Use O(1) extra space besides the returned array if possible.
- Correctly handle zeros and negative numbers.
For example, given `nums = [1, 2, 3, 4]`, return `[24, 12, 8, 6]`.
Follow-up: be ready to explain how your approach behaves when the input contains exactly one zero or multiple zeros.
Constraints
- 0 <= n <= 100000
- -30 <= nums[i] <= 30
- Do not use division
- The final answers fit in a signed 64-bit integer
Examples
Input: ([1, 2, 3, 4],)
Expected Output: [24, 12, 8, 6]
Explanation: For each position, multiply all other values: 2*3*4=24, 1*3*4=12, 1*2*4=8, 1*2*3=6.
Input: ([-1, 2, -3, 4],)
Expected Output: [-24, 12, -8, 6]
Explanation: Negative numbers must be handled correctly: [2*(-3)*4, (-1)*(-3)*4, (-1)*2*4, (-1)*2*(-3)].
Hints
- First store, for each index, the product of all numbers to its left.
- Then scan from right to left while keeping a running suffix product, and multiply it into the current answer.