Product of Array Except Self
MediumPrefix × suffix, no division
Each answer is everything on its left times everything on its right — two sweeps, no division.
The idea
The answer at i is (product of everything left of i) × (product of everything right of i). Sweep once left-to-right for prefixes, once right-to-left multiplying in suffixes.
1
2
3
4
0
1
2
3
Step 1 of 6. Brute force: for each slot, multiply every other element. Values: 1, 2, 3, 4.
1/6
Brute force
timeO(n²)spaceO(1)
Multiply the others.
1for (let i = 0; i < n; i++) {2 let p = 1;3 for (let j = 0; j < n; j++) if (j !== i) p *= nums[j];4 res[i] = p;5}Input
- array
- [1, 2, 3, 4]
Memory
- i
- —
Output
- result
- —
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [1, 2, 3, 4]
- Output:
- [24, 12, 8, 6]
- Explanation:
- Each slot is the product of all the others.
Example 2
- Input:
- nums = [2, 3, 4]
- Output:
- [12, 8, 6]
- Explanation:
- For 2 → 3x4 = 12, and so on.
Example 3
- Input:
- nums = [1, 0]
- Output:
- [0, 1]
- Explanation:
- The 0 makes every other slot's product 0 except its own.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.