Problem link ও উৎস
- **Original source:** Classic prefix/suffix product exercise
- **Platform:** LeetCode —
- **Topic:** array / prefix products
- **Difficulty:** Medium
- **Pattern:** prefix products (বাঁ পাশের product × ডান পাশের product)
- **Basic idea inherited from:** prefix sums, যোগের জায়গায় গুণ বসিয়ে — "এর বাঁয়ের সবকিছু" আর "এর ডানের সবকিছু" আগে জমিয়ে রাখা
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা integer array `nums` দেওয়া। একটা নতুন array `res` বানাও যেখানে `res[i]` = `nums`-এর `i` ছাড়া বাকি সব element-এর গুণফল। শর্ত: **division ব্যবহার করা যাবে না**, আর চাও O(n) time।
```text
nums = [1, 2, 3, 4]
res[0] = 2*3*4 = 24
res[1] = 1*3*4 = 12
res[2] = 1*2*4 = 8
res[3] = 1*2*3 = 6
ফল: [24, 12, 8, 6]
```
### Input ও output {#8-example-input-and-output}
```text
Input : [1, 2, 3, 4] -> [24, 12, 8, 6]
Input : [-1, 1, 0, -3, 3] -> [0, 0, 9, 0, 0] (0 থাকলেও division ছাড়া ঠিক)
Edge case 1 (দুটো element): [2, 3] -> [3, 2]
Edge case 2 (একটাই): [5] -> [1] (নিজেকে বাদ দিলে কেউ নেই -> খালি গুণফল 1)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একসারি মানুষ দাঁড়িয়ে; প্রত্যেকে জানতে চায় "আমাকে বাদ দিয়ে বাকি সবার হাতের টাকার গুণফল কত"। একজন বাঁ দিক থেকে হেঁটে প্রত্যেককে বলে দেয় "তোমার বাঁয়ের সবার গুণফল এই", আরেকজন ডান দিক থেকে হেঁটে সেটাকে "তোমার ডানের সবার গুণফল" দিয়ে গুণ করে দেয়। নিজেকে কখনো গোনা হয় না।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত **prefix sums**, শুধু যোগের জায়গায় গুণ। prefix sum-এ `prefix[i]` = বাঁ পাশের সব element-এর যোগফল; এখানে আমরা রাখি বাঁ পাশের সব element-এর **গুণফল** আর ডান পাশের সব element-এর গুণফল। `res[i]` = বাঁ-গুণফল × ডান-গুণফল। derivation-এর জন্য [../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/](../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/README.md)।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: `i` ছাড়া সবার গুণফল = (`i`-এর বাঁয়ের সবার গুণফল) × (`i`-এর ডানের সবার গুণফল)। division ছাড়া এটা করতে দুই দিক থেকে চলমান গুণফল লাগে — একবার বাঁ থেকে ডানে (prefix), একবার ডান থেকে বাঁয়ে (suffix)। 0 থাকলেও সমস্যা নেই, কারণ আমরা কখনো ভাগ করছি না।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **output array** `res` (সাইজ n), আর দুটো চলমান scalar — `prefix` (বাঁ পাশের গুণফল) ও `suffix` (ডান পাশের গুণফল)। আলাদা prefix/suffix array না রেখে দুটো scalar দিয়েই হয়ে যায়, তাই output বাদে O(1) extra।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Array-র O(1) sequential read/write-এ দুই pass সহজ: প্রথম pass-এ `res[i]`-তে বাঁ পাশের গুণফল বসাই, দ্বিতীয় pass-এ ডান পাশের চলমান গুণফল দিয়ে গুণ করি। চলমান গুণফল একটা variable-এ ধরে রাখা যায় বলে আলাদা structure লাগে না।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা `i`-এর জন্য একটা ভেতরের loop চালিয়ে `i` ছাড়া বাকি সবাইকে গুণ করো।
```text
for i in range(n):
p = 1
for j in range(n):
if j != i:
p *= nums[j]
res[i] = p
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
দুটো nested loop মানে **O(n^2)**। আরেকটা "চালাক" উপায় — সব গুণ করে প্রতিটা `i`-তে `total / nums[i]` — কিন্তু এটা division ব্যবহার করে (problem নিষেধ করেছে) আর কোনো element 0 হলে ভেঙে পড়ে। তাই prefix/suffix পথই সঠিক ও দ্রুত।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: `i` ছাড়া সবার গুণফলকে দুই টুকরোয় ভাঙা যায় — বাঁয়ের সব আর ডানের সব। দুই দিকের চলমান গুণফল আলাদাভাবে জমালে কোনো ভাগ ছাড়াই, এমনকি 0 থাকলেও, প্রতিটা উত্তর পাওয়া যায়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
প্রথম pass বাঁ থেকে ডানে: `res[i]`-তে রাখো `i`-এর বাঁ পাশের সবার গুণফল (`prefix` variable ব্যবহার করে)। দ্বিতীয় pass ডান থেকে বাঁয়ে: `res[i]`-কে `suffix` (ডান পাশের চলমান গুণফল) দিয়ে গুণ করো। দুই pass, O(n) time, output বাদে O(1) space।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "সব গুণ করে ভাগ করব" (division, 0-তে ভাঙে) ভুলে গিয়ে ভাবো "প্রতিটা ঘরের উত্তর = বাঁয়ের গুণফল × ডানের গুণফল।" দুই দিকের prefix-গুণফল জমালেই ভাগ ছাড়া কাজ হয়।
### ছবিতে বোঝা {#7-visual-explanation}
`nums = [1, 2, 3, 4]`:
```text
pass 1 (বাঁ থেকে, res[i] = বাঁয়ের গুণফল):
res = [1, 1, 2, 6] (prefix: 1 -> 1 -> 2 -> 6)
pass 2 (ডান থেকে, × ডানের গুণফল):
i=3: res[3]*=1 -> 6 ; suffix=4
i=2: res[2]*=4 -> 8 ; suffix=12
i=1: res[1]*=12 -> 12; suffix=24
i=0: res[0]*=24 -> 24; suffix=24
ফল: [24, 12, 8, 6]
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `[2, 3]`:
1. pass 1: `prefix=1`। `i=0`: `res[0]=prefix=1`; `prefix*=2 -> 2`। `i=1`: `res[1]=prefix=2`; `prefix*=3 -> 6`। এখন `res=[1, 2]`।
2. pass 2: `suffix=1`। `i=1`: `res[1]*=suffix -> 2*1=2`; `suffix*=nums[1]=3 -> 3`। `i=0`: `res[0]*=suffix -> 1*3=3`; `suffix*=nums[0]=2 -> 6`।
3. ফল: `res=[3, 2]`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def product_except_self(nums):
n = len(nums)
res = [1] * n
prefix = 1 # বাঁ পাশের সবার গুণফল
for i in range(n):
res[i] = prefix
prefix *= nums[i]
suffix = 1 # ডান পাশের সবার গুণফল
for i in range(n - 1, -1, -1):
res[i] *= suffix
suffix *= nums[i]
return res
# ---- tests ----
assert product_except_self([1, 2, 3, 4]) == [24, 12, 8, 6]
assert product_except_self([-1, 1, 0, -3, 3]) == [0, 0, 9, 0, 0]
assert product_except_self([2, 3]) == [3, 2]
assert product_except_self([5]) == [1] # নিজেকে বাদ দিলে খালি গুণফল = 1
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `res = [1] * n` — শুরুতে সব 1; এখানে বাঁ পাশের গুণফল বসবে।
- `prefix = 1` — কোনো element-এর বাঁয়ে কিছু না থাকলে গুণফল 1 (খালি গুণফল)।
- pass 1: `res[i] = prefix` তারপর `prefix *= nums[i]` — আগে বসাই (নিজেকে বাদ), পরে নিজেকে গুণে এগোই।
- `suffix = 1` — ডান পাশের চলমান গুণফল।
- pass 2: `res[i] *= suffix` তারপর `suffix *= nums[i]` — বাঁ-গুণফলকে ডান-গুণফল দিয়ে গুণ।
- `return res` — প্রতিটা ঘরে "নিজেকে বাদ দিয়ে সবার গুণফল"।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[1,2,3,4]` → pass 1 দেয় `[1,1,2,6]`, pass 2 ডান থেকে গুণ করে `[24,12,8,6]`, assert pass। `[-1,1,0,-3,3]` → 0 থাকা সত্ত্বেও ভাগ ছাড়া `[0,0,9,0,0]`; `[2,3]` → `[3,2]`; `[5]` → `[1]`। শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
দুই pass (prefix তারপর suffix) — division ছাড়াই, array result তাই `JSON.stringify` দিয়ে test।
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
const eq = (a, b) => JSON.stringify(a) === JSON.stringify(b);
// res[i] = product of all except nums[i], no division
function productExceptSelf(nums) {
const n = nums.length;
const res = new Array(n).fill(1);
let prefix = 1; // বাঁ পাশের সবার গুণফল
for (let i = 0; i < n; i++) {
res[i] = prefix;
prefix *= nums[i];
}
let suffix = 1; // ডান পাশের সবার গুণফল
for (let i = n - 1; i >= 0; i--) {
res[i] *= suffix;
suffix *= nums[i];
}
return res;
}
// ---- test cases (example + edge) ----
assert(eq(productExceptSelf([1, 2, 3, 4]), [24, 12, 8, 6]), "basic");
assert(eq(productExceptSelf([-1, 1, 0, -3, 3]), [0, 0, 9, 0, 0]), "has-zero"); // edge
assert(eq(productExceptSelf([2, 3]), [3, 2]), "pair");
assert(eq(productExceptSelf([5]), [1]), "single"); // edge
console.log("সব JS test pass!");
```
> **JS টীকা:** `new Array(n).fill(1)` দিয়ে নিরাপদে initialize করো — `new Array(n)` খালি slot রাখে যা `*=`-এ `NaN` দিতে পারে। result array compare-এ `JSON.stringify`। 0 থাকলেও ঠিক, কারণ কোথাও ভাগ করি না।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function productExceptSelf(nums: number[]): number[] {
const n = nums.length;
const res: number[] = new Array