কনটেন্টে যান

014 — Product of Array Except Self

Problem link ও উৎস

  • 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, যোগের জায়গায় গুণ বসিয়ে — "এর বাঁয়ের সবকিছু" আর "এর ডানের সবকিছু" আগে জমিয়ে রাখা

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

একটা 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]

Input ও 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)

চেনা উদাহরণে বোঝা

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

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

ভিত prefix sums, শুধু যোগের জায়গায় গুণ। prefix sum-এ prefix[i] = বাঁ পাশের সব element-এর যোগফল; এখানে আমরা রাখি বাঁ পাশের সব element-এর গুণফল আর ডান পাশের সব element-এর গুণফল। res[i] = বাঁ-গুণফল × ডান-গুণফল। derivation-এর জন্য ../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/।

ভেতরের যুক্তি

লুকানো logic: i ছাড়া সবার গুণফল = (i-এর বাঁয়ের সবার গুণফল) × (i-এর ডানের সবার গুণফল)। division ছাড়া এটা করতে দুই দিক থেকে চলমান গুণফল লাগে — একবার বাঁ থেকে ডানে (prefix), একবার ডান থেকে বাঁয়ে (suffix)। 0 থাকলেও সমস্যা নেই, কারণ আমরা কখনো ভাগ করছি না।

কী দিয়ে তথ্য রাখব

একটা output array res (সাইজ n), আর দুটো চলমান scalar — prefix (বাঁ পাশের গুণফল) ও suffix (ডান পাশের গুণফল)। আলাদা prefix/suffix array না রেখে দুটো scalar দিয়েই হয়ে যায়, তাই output বাদে O(1) extra।

এটি কেন উপযুক্ত

Array-র O(1) sequential read/write-এ দুই pass সহজ: প্রথম pass-এ res[i]-তে বাঁ পাশের গুণফল বসাই, দ্বিতীয় pass-এ ডান পাশের চলমান গুণফল দিয়ে গুণ করি। চলমান গুণফল একটা variable-এ ধরে রাখা যায় বলে আলাদা structure লাগে না।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

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

উদাহরণ
for i in range(n):
    p = 1
    for j in range(n):
        if j != i:
            p *= nums[j]
    res[i] = p

কোথায় বেশি কাজ হচ্ছে

দুটো nested loop মানে O(n^2)। আরেকটা "চালাক" উপায় — সব গুণ করে প্রতিটা i-তে total / nums[i] — কিন্তু এটা division ব্যবহার করে (problem নিষেধ করেছে) আর কোনো element 0 হলে ভেঙে পড়ে। তাই prefix/suffix পথই সঠিক ও দ্রুত।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: i ছাড়া সবার গুণফলকে দুই টুকরোয় ভাঙা যায় — বাঁয়ের সব আর ডানের সব। দুই দিকের চলমান গুণফল আলাদাভাবে জমালে কোনো ভাগ ছাড়াই, এমনকি 0 থাকলেও, প্রতিটা উত্তর পাওয়া যায়।

আরও কম কাজে সমাধান

প্রথম pass বাঁ থেকে ডানে: res[i]-তে রাখো i-এর বাঁ পাশের সবার গুণফল (prefix variable ব্যবহার করে)। দ্বিতীয় pass ডান থেকে বাঁয়ে: res[i]-কে suffix (ডান পাশের চলমান গুণফল) দিয়ে গুণ করো। দুই pass, O(n) time, output বাদে O(1) space।

ভাবনার পরিবর্তন

মোচড়: "সব গুণ করে ভাগ করব" (division, 0-তে ভাঙে) ভুলে গিয়ে ভাবো "প্রতিটা ঘরের উত্তর = বাঁয়ের গুণফল × ডানের গুণফল।" দুই দিকের prefix-গুণফল জমালেই ভাগ ছাড়া কাজ হয়।

ছবিতে বোঝা

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]

ছোট input-এ ধাপে ধাপে

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

কোড ও ব্যাখ্যা

Python

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!")

কোডের প্রতিটি অংশ

  • 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 মিলিয়ে দেখা

[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

দুই 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

TypeScript
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 টাইপেও সুরক্ষিত।

খরচ ও সাধারণ ভুল

সময়

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

অতিরিক্ত জায়গা

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

যে ভুলগুলো এড়াতে হবে

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

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

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

পরের অনুশীলন

কৌশলটি মনে রাখুন

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

নিজেকে যাচাই করুন

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

কোথায় কাজে লাগে

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