014 — Product of Array Except Self¶

Source¶

Original source: Classic prefix/suffix product exercise
Platform: LeetCode — https://leetcode.com/problems/product-of-array-except-self/
Topic: array / prefix products
Difficulty: Medium
Pattern: prefix products (বাঁ পাশের product × ডান পাশের product)
Basic idea inherited from: prefix sums, যোগের জায়গায় গুণ বসিয়ে — "এর বাঁয়ের সবকিছু" আর "এর ডানের সবকিছু" আগে জমিয়ে রাখা

1. Problem in simple words¶

একটা integer array nums দেওয়া। একটা নতুন array res বানাও যেখানে res[i] = nums-এর i ছাড়া বাকি সব element-এর গুণফল। শর্ত: division ব্যবহার করা যাবে না, আর চাও O(n) time।

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]

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/।

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 লাগে না।

6. Real-life analogy¶

ভাবো একসারি মানুষ দাঁড়িয়ে; প্রত্যেকে জানতে চায় "আমাকে বাদ দিয়ে বাকি সবার হাতের টাকার গুণফল কত"। একজন বাঁ দিক থেকে হেঁটে প্রত্যেককে বলে দেয় "তোমার বাঁয়ের সবার গুণফল এই", আরেকজন ডান দিক থেকে হেঁটে সেটাকে "তোমার ডানের সবার গুণফল" দিয়ে গুণ করে দেয়। নিজেকে কখনো গোনা হয় না।

7. Visual explanation¶

nums = [1, 2, 3, 4]:

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]

8. Example input and output¶

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)

9. Brute force thinking¶

প্রথম সরল চিন্তা: প্রতিটা i-এর জন্য একটা ভেতরের loop চালিয়ে i ছাড়া বাকি সবাইকে গুণ করো।

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-গুণফল জমালেই ভাগ ছাড়া কাজ হয়।

14. Step-by-step dry run¶

Input [2, 3]:

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]।
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।
ফল: res=[3, 2]।

15. Python solution¶

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 — প্রতিটা ঘরে "নিজেকে বাদ দিয়ে সবার গুণফল"।

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!।

18. Time complexity¶

O(n) — দুটো আলাদা single pass; কোনো nested loop নেই।

19. Space complexity¶

O(1) extra — output res ছাড়া শুধু দুটো scalar (prefix, suffix); output সাধারণত extra হিসেবে গোনা হয় না।

20. Common mistakes¶

division ব্যবহার করে total / nums[i] করা — problem নিষেধ করেছে, আর কোনো element 0 হলে ভেঙে পড়ে।
pass 1-এ prefix *= nums[i] আগে করে তারপর res[i] = prefix বসানো — তখন নিজেকেও গুণ করে ফেলবে; আগে বসাও, পরে গুণ করো।
suffix pass ভুল দিকে চালানো (বাঁ থেকে ডানে) — ডান পাশের গুণফল পেতে অবশ্যই ডান থেকে বাঁয়ে যেতে হবে।

21. Which basic problem this inherits from¶

ভিত্তি: prefix sums (math level 5), যোগের জায়গায় গুণ। Static Range Sum (#9)-এর মতোই "একদিকের চলমান aggregate জমিয়ে রাখা", শুধু দুই দিক থেকে। chapter-এর ../patterns.md-এর "Pattern 3 — Prefix Sums" দেখো।

22. Similar harder problems¶

Subarray Sum Equals K (prefix sum + hash map) — https://leetcode.com/problems/subarray-sum-equals-k/ (#15)
Maximum Product Subarray — https://leetcode.com/problems/maximum-product-subarray/
Find Pivot Index (prefix sum দিয়ে balance) — https://leetcode.com/problems/find-pivot-index/

23. Pattern learned¶

Prefix (এবং suffix) products: "নিজেকে বাদ দিয়ে aggregate, division ছাড়া" দেখলে দুই দিক থেকে চলমান গুণফল জমাও — res[i] = বাঁ × ডান। prefix-sum চিন্তারই গুণ-সংস্করণ, O(n)।

24. Final summary¶

ভবিষ্যতের আমাকে: "res[i] = বাঁয়ের গুণফল × ডানের গুণফল; দুই pass, division নয়।" "product except self / নিজেকে বাদ দিয়ে aggregate" দেখলেই prefix-suffix চিন্তা মনে করবে — O(n) time, O(1) extra।

25. JavaScript solution (with test cases)¶

দুই pass (prefix তারপর suffix) — division ছাড়াই, array result তাই JSON.stringify দিয়ে test।

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 থাকলেও ঠিক, কারণ কোথাও ভাগ করি না।

26. TypeScript solution (with test cases)¶

function productExceptSelf(nums: number[]): number[] {
  const n = nums.length;
  const res: number[] = new Array<number>(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;
}
function expectArr(actual: number[], exp: number[], msg = ""): void {
  if (JSON.stringify(actual) !== JSON.stringify(exp))
    throw new Error(`FAIL ${msg}: got ${JSON.stringify(actual)}`);
}
expectArr(productExceptSelf([1, 2, 3, 4]), [24, 12, 8, 6], "basic");
expectArr(productExceptSelf([-1, 1, 0, -3, 3]), [0, 0, 9, 0, 0], "has-zero");
expectArr(productExceptSelf([5]), [1], "single");
console.log("সব TS test pass!");

TS টীকা: new Array<number>(n) generic দিয়ে element type পাকা হয়, তাই prefix/suffix গুণে কখনো string মিশে যাবে না — division-free invariant টাইপেও সুরক্ষিত।

27. কোথায় কাজে লাগে (real-world use)¶

Probability/likelihood: প্রতিটা সদস্য বাদে বাকিদের যৌথ probability (leave-one-out product) — division ছাড়াই, 0-probability থাকলেও নিরাপদ।
Sensor fusion / weights: প্রতিটা feature বাদ দিয়ে বাকিদের combined weight বের করা।
Spreadsheet engines: "এই cell বাদে product" টাইপ aggregate column compute।
Image kernels: prefix/suffix product দিয়ে running multiplicative filter।
Risk modeling: এক factor বাদে বাকিদের multiplicative effect হিসাব।
Inventory/pricing: এক item বাদ দিয়ে বাকিদের combined multiplier বের করা।

মূল pattern: prefix × suffix জমিয়ে রাখা (prefix-sum-এর গুণ-সংস্করণ) — "নিজেকে বাদ দিয়ে aggregate, division নয়" দেখলেই এই দুই-pass।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।