Prefix Sumprefix sum · range sum · prefix + hash map · 2D prefix

في الفصل اللي فات (Sliding Window) شفت إن الـ window بيقع أول ما يبقى فيه أرقام سالبة، لأن تكبير الـ window ممكن يصغّر المجموع. دلوقتي هنتعلم الأداة اللي بتشتغل في الحالة دي بالظبط: بتجمع الـ array مرة واحدة in one pass، وبعدها مجموع أي subarray يبقى طرحة واحدة. ولو حطيت جنبها hash map، تعدّ الـ subarrays اللي مجموعها k حتى مع السالب.

هتطلع من الفصل ده وإنت عارف

  • تبني prefix array طوله n + 1، وتعرف ليه الخانة الزيادة دي بتشيل if و bugs.
  • تكتب prefix[r + 1] - prefix[l] من دماغك، وتشتقها لو نسيتها، من غير off-by-one.
  • تفهم ليه prefix + hash map بيعدّ الـ subarrays مع السالب، وليه الـ map بتبدأ بـ {0: 1}، وليه بنسأل قبل ما نسجّل.
  • تحل 303 و 724 و 238 و 560 و 525 و 974، كل واحدة بتزوّد فكرة واحدة على اللي قبلها.

ليه Prefix Sum؟

خد المسألة دي: array ثابتة، وهتتسأل queries كتير من النوع ده: «مجموع العناصر من l لـ r كام؟». أول حل بييجي في دماغك: loop لكل query.

صح، بس كل query بتاخد O(n). مع n = 100,000 عنصر و q = 100,000 query، ده 10 مليار عملية في الـ worst case، يعني TLE أكيد. بص عليه على 3 queries بس:

المشكلة إننا بنجمع نفس الأرقام تاني وتالت، وبنرمي المجموع كل مرة. الـ key insight: نجمع مرة واحدة من الأول للآخر، ونحفظ المجموع عند كل خطوة. بعدها أي query تبقى طرحة.

تشبيه إنت مسافر إسكندرية على الصحراوي، وعند كل بنزينة بتكتب قراية عداد الكيلومترات. لو حد سألك «المسافة بين البنزينة التالتة والسادسة كام؟»، مش هتجمع المسافات الصغيرة. هتطرح: العداد عند السادسة ناقص العداد عند التالتة. والعداد كان على صفر قبل ما تتحرك من البيت. الصفر ده هو الخانة الزيادة اللي هنتكلم عنها كتير.

النتيجة: build في O(n) مرة واحدة، وكل query في O(1). يعني حوالي 200,000 عملية بدل 10 مليار.

طب إزاي تعرف من كلام المسألة إنها محتاجة prefix sum أصلًا؟

إزاي تعرفه من المسألة

أي مسألة فيها مجموع جزء متصل (subarray، مش subsequence) مرشّحة لـ prefix sum. الكلمات دي بتقولك كده:

لما تشوف: range sum querysum between i and jmany queries, array never changes count subarrays with sum knegative numbers allowedsum divisible by k equal number of 0s and 1sleft sum equals right sumproduct of all except selfsum of a sub-rectangle
ومش هو غالبًا لو: the array is updated between querieslongest / shortest window, all positivesubsequence (not contiguous)

لو الـ array بتتعدّل بين الـ queries، كل update محتاج يعيد بناء الـ prefix في O(n)، والحل الصح Fenwick tree أو segment tree. ولو كله موجب والمطلوب أطول أو أقصر window، الـ sliding window أحسن لأنه O(1) memory. ولو subsequence، العناصر مش متصلة أصلًا، والطرح مالوش معنى.

النوعالفكرةبتخزّن إيهمسائل
مجموع rangeprefix[r + 1] - prefix[l]prefix array طوله n + 11480، 303، 304
شمال ويميناليمين = الكل - الشمال - العنصرمتغيّرين بس724
حاصل ضربضرب الشمال × ضرب اليمينprefix و suffix products238
عدّ subarrays بمجموع معيّنعايز prefix قديم قيمته sum - kmap: قيمة → count560، 930، 1248
أطول subarray بشرطنفس الـ sum اتكرر = اللي بينهم مجموعه 0map: قيمة → أول index525
باقي القسمةنفس الباقي = الفرق بيقبل القسمةcount لكل باقي974، 523
flowchart TD
  A["Contiguous subarray + sum?"] --> B{"Array updated between queries?"}
  B -- yes --> T["Fenwick / segment tree"]
  B -- no --> C{"Many range-sum queries?"}
  C -- yes --> P["Prefix array of n + 1, O(1) per query"]
  C -- no --> D{"Count or longest with an exact sum, negatives allowed?"}
  D -- yes --> H["Prefix sum + hash map"]
  D -- no --> E{"All positive, longest or shortest window?"}
  E -- yes --> W["Sliding window"]
  E -- no --> X["Left / right totals, or prefix x suffix"]
  

اسأل نفسك الأسئلة دي بالترتيب ده.

عرفت إمتى تستخدمه. نبدأ من الأساس: إزاي تبني الـ prefix، وليه طوله n + 1 مش n؟

بناء الـ prefix array، وليه طوله n + 1

التعريف اللي هنمشي عليه طول الفصل prefix[i] = مجموع أول i عناصر، يعني nums[0] + ... + nums[i - 1]. الـ i هنا عدد عناصر، مش index في nums.

يعني prefix[0] = مجموع ولا حاجة = 0 (الـ empty prefix، زي العداد قبل ما العربية تتحرك)، و prefix[n] = مجموع الـ array كلها. من 0 لـ n دول n + 1 قيمة. والخانة الزيادة دي sentinel: هي اللي هتخلّي صيغة الـ range واحدة لكل الحالات من غير if.

  1. n + 1 خانة: واحدة لكل عدد عناصر من 0 لـ n. والـ .fill(0) مهم: new Array(7) لوحدها خاناتها undefined، فأول سطر في الـ loop هيعمل undefined + 2 = NaN، silent bug يبوّظ كل اللي بعده.
  2. ليه i < n مش i <= n؟ الـ i هنا index في nums، وآخر index فيها n - 1. لو كتبت <= هتقرا nums[n] = undefined وتكتب NaN في خانة زيادة. السؤال اللي يحميك: الـ i دي index في أنهي array؟
  3. الجديد = اللي قبله + عنصر واحد، مش بنجمع من الأول كل مرة، وده اللي بيخلّي الـ build O(n). وبنكتب في i + 1 لأن الـ prefix "متأخر" عن nums بخانة.
  4. prefix[n] هو مجموع الكل، معلومة هتحتاجها في Find Pivot Index.

الصف التاني هو prefix. لاحظ إن prefix[i] واقف تحت nums[i] في الرسمة، بس معناه مجموع اللي قبل nums[i]:

عندك الـ prefix. طب إزاي تطلّع منه مجموع range معيّن في طرحة واحدة؟

مجموع أي range في O(1)

عايز nums[l] + ... + nums[r] والاتنين داخلين. ما تحفظش الصيغة، اشتقها مرة وإنت فاهم:

يعني prefix[r + 1] فيه اللي عايزه وزيادة من قدّام، والزيادة دي هي أول l عناصر = prefix[l]. اطرحها، يفضل اللي عايزه بالظبط.

  1. l و r indices من 0، والاتنين داخلين. ده الشكل اللي LeetCode بيدّيه غالبًا.
  2. ليه r + 1؟ prefix[r] بيقف عند nums[r - 1]، يعني nums[r] مش جوّاه. محتاجين أول r + 1 عناصر.
  3. ليه prefix[l] مش prefix[l - 1]؟ اللي بنشيله هو اللي قبل l، وده أول l عناصر بالظبط. ولما l = 0، prefix[0] = 0 فمفيش حاجة بتتشال، من غير if.
  4. طرحة واحدة، O(1) مهما كان الـ range طويل. الكبير ناقص الصغير، مش العكس.

3 queries: واحدة في النص، وواحدة بتبدأ من 0، وواحدة عنصر واحد. الأحمر هو اللي بنطرحه:

الفكرة اللي لازم تفضل معاك أي جزء متصل = فرق بين اتنين prefix. كل حاجة جاية في الفصل، حتى عدّ الـ subarrays، مبنية على الجملة دي.

الـ prefix طوله n + 1. عايز مجموع nums[2..5] (الاتنين داخلين). تكتب إيه؟

  • prefix[5] - prefix[2]
  • prefix[6] - prefix[2]
  • prefix[6] - prefix[1]
  • prefix[5] - prefix[1]

prefix[6] = nums[0..5]، و prefix[2] = nums[0..1]، والفرق = nums[2..5]. الأول ناقصه nums[5]، والتالت فيه nums[1] زيادة.

الصيغة سهلة، لحد ما تقابل حل مكتوب بشكل تاني، أو مسألة بتعدّ من 1. منين بييجي الـ off-by-one بالظبط؟

0-indexed و 1-indexed: منين بييجي الـ off-by-one

هتلاقي الـ prefix sum مكتوب بأكتر من شكل في الحلول، ودي أكبر مصدر للخلبطة:

الشكلالتعريفمجموع l..rالفخ
طول n + 1 (بتاعنا)prefix[i] = أول i عناصرprefix[r+1] - prefix[l]ولا حاجة، صيغة واحدة لكل الحالات.
نفس الطول npre[i] = nums[0..i] والـ i داخلpre[r] - pre[l-1]لما l = 0: pre[-1] = undefined، والنتيجة NaN.
المسألة بتعدّ من 1"من العنصر رقم L للعنصر رقم R"prefix[R] - prefix[L-1]لو استخدمت R + 1 هنا هتزحلق خانة.

مش غلط، بس لازم تفتكر الـ edge case كل مرة، و JS مش هتنبّهك لو نسيت: pre[-1] بيرجع undefined عادي، و 5 - undefined = NaN. عشان كده الدليل بيستخدم n + 1 دايمًا.

وحتى loop الـ build ليها شكلين صح، والـ < بتتغيّر حسب الـ i ماشية على أنهي array:

قاعدة تمشي بيها لو المسألة بتعدّ من 1، ما تحفظش صيغة تانية. حوّل الأول (l = L - 1 و r = R - 1)، واستخدم نفس prefix[r + 1] - prefix[l]. صيغة واحدة في دماغك أأمن من تلاتة.

تمام في 1D. طب نفس الفكرة تنفع على matrix؟

Prefix Sum في 2D (باختصار)

نفس الفكرة: P[r][c] = مجموع المستطيل من (0, 0) لـ (r - 1, c - 1)، بصف زيادة وعمود زيادة أصفار عشان الحواف. الـ trick كله اسمه inclusion-exclusion: لما تجمع المستطيل اللي فوق واللي على الشمال، الحتة المشتركة بتتجمع مرتين، فتطرحها مرة. هتحتاجه في LeetCode 304، والـ grids عمومًا في Graphs على Grid.

  1. فخ JS مشهور: new Array(rows + 1).fill(new Array(cols + 1).fill(0)) بيحط نفس الـ array الداخلية في كل الصفوف، فتعديل صف بيعدّل الكل. Array.from مع function بتعمل array جديدة لكل صف.
  2. بنلف على خانات الـ matrix (< rows و < cols)، وبنكتب في P[r + 1][c + 1] لأن الـ P متأخرة خانة في الاتجاهين.
  3. الخانة + المستطيل اللي فوق + اللي على الشمال، والاتنين فيهم الركن P[r][c] مرتين، فبنطرحه مرة.
  4. الكبير، ناقص الشريط اللي فوق، ناقص الشريط اللي على الشمال. الركن اتطرح مرتين، فبنرجّعه بـ + P[r1][c1]. وكل + 1 جاي من نفس قاعدة الـ 1D.

الشبكة هي P، والصفوف تحتها هي الـ matrix. الأخضر الخانة الجديدة، والـ teal اللي بنجمعه، والأحمر الركن اللي بنطرحه:

التعقيد: الـ build O(rows × cols)، وكل query O(1).

كده الأدوات كلها معاك. نطبّقها على أول مسألة حقيقية فيها queries كتير.

مثال محلول 1: Range Sum Query - Immutable

Range Sum Query - Immutable

easyLeetCode 303

اعمل class بتاخد array أرقام مرة واحدة في الـ constructor، وبعدها بتجاوب نداءات كتير لـ sumRange(left, right): مجموع العناصر من left لـ right والاتنين داخلين. الـ array مش بتتغيّر، والنداءات ممكن توصل 10⁴.

nums = [4, -2, 7, 1, -3, 5] sumRange(1, 3) → 6 (-2 + 7 + 1) sumRange(0, 5) → 12 (whole array) sumRange(4, 4) → -3 (one element)

ده التطبيق المباشر للي فات. الجديد هنا إن الحل class: الـ precompute في الـ constructor مرة واحدة، والـ query في method بتتنادى كتير.

نفكّر فيها مع بعض

  1. Brute force: loop جوه sumRange، يعني O(n) لكل نداء، و 10⁸ في الـ worst case.
  2. الـ key insight: الـ array ثابتة، فـ build مرة في الـ constructor بـ O(n)، وكل نداء طرحة O(1).
  3. الخطة: نخزّن الـ prefix على الـ object نفسه (this.prefix) عشان sumRange يشوفه.
  4. Edge cases: left = 0، و left = right، والـ array كلها، وأرقام سالبة.
  1. LeetCode ساعات بيدّيك القالب القديم: var NumArray = function(nums) {...} و NumArray.prototype.sumRange = .... نفس الكلام بالظبط، استخدم اللي القالب بيدّيهولك.
  2. ليه this.prefix مش const prefix؟ الـ const بيموت لما الـ constructor يخلص، و sumRange هيضرب ReferenceError. الـ this بيخزّنه على الـ object.
  3. نفس loop الـ build، وبتشتغل مرة واحدة مهما كان عدد النداءات.
  4. نفس الصيغة: right + 1 عشان right داخل، و left من غير - 1.
النداءالمتوقعليه الحالة دي مهمة
sumRange(0, 5)12left = 0: prefix[0] = 0 بيمنع الـ NaN
sumRange(4, 4)-3عنصر واحد: الفرق بين خانتين جنب بعض
sumRange(1, 3)6range في النص، والسالب جوّاه
nums = [7], sumRange(0, 0)7عنصر واحد في الـ array: الـ prefix طوله 2

التعقيد: الـ constructor O(n) وقت و memory، وكل sumRange O(1). يعني q نداء = O(n + q) بدل O(n × q).

في الانترفيو لو اتسألت "طب لو الـ array بتتغيّر؟": كل update محتاج يعدّل كل الـ prefix اللي بعده، O(n). الحل ساعتها Fenwick أو segment tree بـ O(log n). مش لازم تكتبهم، بس لازم تعرف إن ده حدّ الـ prefix sum.

هنا خزّنّا prefix array كامل. طب لو كل اللي محتاجه لكل index هو مجموع شماله ومجموع يمينه، محتاج array أصلًا؟

مثال محلول 2: Find Pivot Index

Find Pivot Index

easyLeetCode 724

دوّر على أول index من الشمال يكون مجموع اللي على شماله بيساوي مجموع اللي على يمينه. العنصر نفسه مش محسوب في أي ناحية، والناحية الفاضية مجموعها 0. لو مفيش، رجّع -1.

Input: [2, 3, -1, 8, 4] → 3 (2 + 3 - 1 = 4 = 4) Input: [1, 2, 3] → -1 Input: [2, 1, -1] → 0 (left is empty = 0, right = 1 - 1 = 0)

الجديد هنا إن مش محتاجين prefix array خالص: الشمال running sum بنحسبه on the fly، واليمين = total - left - nums[i].

نفكّر فيها مع بعض

  1. Brute force: لكل index، loop للشمال و loop لليمين. O(n²).
  2. بالـ prefix array: الشمال prefix[i] واليمين prefix[n] - prefix[i + 1]. O(n) بس بـ O(n) memory.
  3. الـ key insight: اليمين = الكل - الشمال - العنصر. فلو معانا total مرة، و leftSum بيكبر وإحنا ماشيين، يبقى O(1) memory. الـ leftSum ده هو prefix[i] بالظبط.
  4. Edge cases: الـ pivot عند index 0 أو آخر index، وعنصر واحد (الإجابة 0)، وأرقام سالبة.
  1. مجموع الكل في one pass، وده prefix[n] من غير array. لو كتبتها بـ reduce، ما تنساش الـ 0: reduce على array فاضية من غير initial value بيضرب error.
  2. leftSum = 0 لأن شمال index 0 فاضي. نفس prefix[0] = 0.
  3. ليه - nums[i]؟ الـ pivot مش في أي ناحية. من غيره هتقارن الشمال باليمين + الـ pivot.
  4. أول تساوي نعمل early return، وبما إننا ماشيين من الشمال، ده الـ leftmost.
  5. ليه بعد المقارنة؟ الـ invariant وقت المقارنة: leftSum = مجموع nums[0..i-1] بالظبط. لو ضفت قبل الـ if، الـ pivot هيتحسب في الشمال.
  6. لفّينا كله ومفيش تساوي.

الشمال متعلّم seen، واليمين جوه الـ range، والـ i الحالي بالأصفر:

Inputالمتوقعليه الحالة دي مهمة
[2, 1, -1]0الشمال فاضي = 0، واليمين 1 + (-1) = 0
[5]0عنصر واحد: الناحيتين فاضيين
[1, 2, 3]-1مفيش pivot
[-1, -1, 0, 1, 1, 0]5الـ pivot آخر عنصر: اليمين فاضي

التعقيد: لفّتين، O(n) وقت و O(1) memory.

نفس فكرة الشمال واليمين، بس لو العملية ضرب مش جمع، والقسمة ممنوعة؟

مثال محلول 3: Product of Array Except Self

Product of Array Except Self

mediumLeetCode 238

رجّع array جديدة، كل خانة i فيها حاصل ضرب كل العناصر ما عدا nums[i]. ممنوع القسمة، والمطلوب O(n).

Input: [2, 3, 4, 5] → [60, 40, 30, 24] Input: [3, 2, 0, 4] → [0, 0, 24, 0]

الجديد هنا إن اليمين مش هينفع يتحسب بطرح من الـ total زي 724 (الطرح هنا يبقى قسمة، وممنوعة)، فبنحسبه بـ pass تانية من الآخر: suffix product.

نفكّر فيها مع بعض

  1. Brute force: لكل i اضرب كل اللي غيره. O(n²).
  2. ليه مش القسمة؟ غير إنها ممنوعة، بتقع مع الصفر: في [3, 2, 0, 4] الضرب الكلي 0، و 0 / 0 = NaN، والصح إن خانة الصفر إجابتها 24.
  3. الـ key insight: كل حاجة ما عدا i = (ضرب الشمال) × (ضرب اليمين). الشمال prefix product، واليمين suffix product.
  4. الخطة: pass من الشمال تكتب ضرب الشمال في answer، و pass من الآخر بمتغيّر right تضرب فيه. كده الـ memory الزيادة O(1) (الـ output مش بيتحسب).
  1. طولها n بالظبط، خانة لكل عنصر، مش n + 1، لأنها الإجابة نفسها.
  2. ليه left = 1؟ ضرب ولا حاجة = 1، زي ما مجموع ولا حاجة = 0. ده الـ empty prefix بتاع الضرب، ولو بدأت بـ 0 كل الإجابات هتبقى 0.
  3. الترتيب هو الحل كله: نكتب left الأول، وبعدين نضرب فيه nums[i]. لو قلبتهم، كل خانة هتاخد العنصر بتاعها معاها.
  4. ليه i >= 0 مش i > 0؟ index 0 لازم ياخد نصيبه من اليمين برضه، وإلا answer[0] هيفضل 1. والبداية n - 1 لأنه آخر index.
  5. *= مش =: الخانة فيها ضرب الشمال، وإحنا عايزين الشمال × اليمين.
  6. نفس فكرة السطر 7: nums[i] يدخل في right بعد ما استخدمناه.
Inputالمتوقعليه الحالة دي مهمة
[2, 3, 4, 5][60, 40, 30, 24]الحالة العادية
[3, 2, 0, 4][0, 0, 24, 0]صفر واحد: خانته بس مش صفر. القسمة كانت هتقع هنا
[0, 2, 0][0, 0, 0]صفرين: كل خانة فيها صفر من الناحية التانية
[-1, 0, 2][0, -2, 0]JS بيطلّع -0 في الآخر (-1 × 0)، بس -0 === 0 و JSON.stringify بيكتبه 0، فالـ judge بيقبله

التعقيد: لفّتين، O(n) وقت و O(1) memory زيادة.

في الانترفيو ابدأ بنسخة الـ arrays التلاتة (leftProd و rightProd و answer) لأنها أوضح، وقول إنها O(n) memory، وبعدين optimize للنسخة دي. الـ interviewer عايز يشوفك بتوصل للتحسين.

لحد هنا كل مسألة بتسأل عن range أو index معيّن. طب لو المطلوب تعدّ كل الـ subarrays اللي مجموعها k، والأرقام فيها سالب؟

Prefix Sum + Hash Map: عدّ الـ subarrays

ده المكان اللي الـ sliding window وقع فيه. خد [3, -3, 3] و k = 3: الإجابة 3 ([3] الأولى، و [3, -3, 3]، و [3] التالتة). الـ window بيمسك بداية واحدة لكل نهاية، فبيطلّع 2. مع السالب، أكتر من بداية ممكن تنفع لنفس النهاية، والتصغير مالوش قاعدة.

الـ key insight: كل subarray = فرق بين اتنين prefix

يعني لكل نهاية، السؤال بقى: كام prefix قبلها قيمته prefix[j] - k؟ وده نفس سؤال Two Sum: "شفت الـ complement قبل كده؟"، بس بفرق بدل مجموع، وبـ count بدل وجود. شوف النسخة البطيئة اللي بتجرّب كل زوج prefixes:

الـ loop الداخلية بتسأل سؤال واحد بس: "كام prefix[i] قيمته كذا؟". ده بالظبط اللي الـ hash map بتجاوبه في O(1)، لو خزّنّا فيها كل قيمة prefix شفناها وعدد مراتها.

تشبيه رصيدك في البنك بعد كل عملية هو prefix sum. لو رصيدك النهارده 500 وكان في يوم 300، يبقى من اليوم ده لحد النهارده صافي اللي دخلك 200، حتى لو سحبت وحطيت في النص. عايز تعرف كام فترة بتخلص النهارده صافيها 200؟ اسأل كشكولك: "رصيدي كان 300 كام مرة؟".

ليه الـ map بتبدأ بـ {0: 1}؟

في النسخة البطيئة، prefix[0] = 0 كان في الـ array، وهو اللي بيمثّل البدايات من index 0. الـ map بتبدأ فاضية، فلازم نحطه بإيدنا. من غيره، [3] مع k = 3 هتطلع 0 بدل 1. نفس فكرة الـ n + 1 بشكل map.

وليه count مش Set؟

لأن القيمة بتتكرر، وكل تكرار بداية مختلفة. في الـ animation، القيمة 2 ظهرت في prefix[3] و prefix[5]، فلما prefix[6] = 5 سأل عن 2 لقى اتنين، يعني 2 subarrays. الـ Set كانت هتعدّ واحد.

الـ loop الداخلية دي هي اللي هنشيلها بـ map. إزاي الكود بيبقى one pass؟

مثال محلول 4: Subarray Sum Equals K

Subarray Sum Equals K

mediumLeetCode 560

عدّ كل الـ subarrays المتصلة (فيها عنصر واحد على الأقل) اللي مجموعها k بالظبط. الأرقام ممكن تبقى سالبة أو صفر.

Input: nums = [1, 2, -1, 2, -2, 3], k = 3 → 4 ([1, 2], [2, -1, 2], [2, -2, 3], [3]) Input: nums = [0, 0, 0], k = 0 → 6

الجديد هنا إن الـ map بتجاوب "كام prefix قديم قيمته sum - k؟" في O(1)، بدل الـ loop الداخلية.

نفكّر فيها مع بعض

  1. Brute force: لكل بداية، مجموع جاري لحد الآخر. O(n²) وقت و O(1) memory. قوله كبداية.
  2. ليه مش sliding window؟ السالب: تكبير الـ window ممكن يصغّر المجموع، وأكتر من بداية تنفع.
  3. الخطة: sum جاري، ولكل عنصر: count += seen.get(sum - k)، وبعدين سجّل sum.
  4. Edge cases: subarray من index 0 (محتاج {0: 1})، و k = 0 (محتاج نسأل قبل ما نسجّل)، وأصفار كتير (محتاجين count).
  1. الـ map: قيمة prefix ← count. الـ 0 مرة واحدة هو الـ empty prefix، ومن غيره البدايات من index 0 ما تتعدّش. والـ Map أنضف من object: المفاتيح بتفضل أرقام، ومفيش prototype keys.
  2. sum هو الـ running prefix، بيبدأ 0 لنفس السبب.
  3. بعد السطر ده sum = prefix[j] للنهاية الحالية.
  4. sum - k مش k - sum: من الجبر prefix[i] = prefix[j] - k. لو شكّيت، جرّب [3] و k = 3: الـ need لازم يطلع 0.
  5. الـ || 0 عشان get بيرجّع undefined لو مش موجود، و count += undefined = NaN للأبد. و += مش ++: لو need اتشافت 3 مرات، دول 3 بدايات مختلفة.
  6. ليه بعد العدّ؟ الـ invariant: الـ map فيها الـ prefixes اللي قبل النهاية الحالية بس. لو سجّلت الأول ومع k = 0، هتلاقي نفسك وتعدّ subarray فاضي: [1, 2, 3] هتطلع 3 بدل 0.

الأخضر في الـ map هو الـ need اللي لقيناه، والأصفر الـ sum اللي بنسجّله:

Inputالمتوقعليه الحالة دي مهمة
[3], k = 31من غير {0: 1} هتطلع 0
[1, 2, 3], k = 00لو سجّلت قبل ما تعدّ هتطلع 3
[0, 0, 0], k = 06القيمة 0 بتتكرر، والـ count بيكبر
[1, -1, 1, -1], k = 04بـ Set بدل count هتطلع 3
[3, -3, 3], k = 33الـ sliding window هنا بيطلّع 2

التعقيد: one pass، وكل عملية على الـ Map O(1) average، يعني O(n) وقت، و O(n) memory للـ map.

في الانترفيو هتتسأل غالبًا: "ليه مش sliding window؟" و "ليه {0: 1}؟". جاوب الأول بـ [3, -3, 3]، والتاني بـ [3] و k = 3. مثال صغير بيقنع أكتر من أي كلام.

هنا الـ map كانت بتعدّ. طب لو المطلوب أطول subarray مش عددهم؟

مثال محلول 5: Contiguous Array

Contiguous Array

mediumLeetCode 525

array فيها 0 و 1 بس. رجّع طول أطول subarray متصل فيه عدد الأصفار بيساوي عدد الوحايد، أو 0 لو مفيش.

Input: [0, 0, 1, 0, 1, 1, 1] → 6 ([0, 0, 1, 0, 1, 1]: three 0s, three 1s) Input: [0, 0, 0] → 0 Input: [0, 1, 0, 1] → 4

الجديد هنا إن المطلوب أطول مش عدد، فالـ map بتخزّن أول index لكل sum بدل count، وتبدأ {0: -1} بدل {0: 1}. وعشان نوصل لـ "مجموع = 0" بنعمل transform صغير: الـ 0 يبقى -1.

نفكّر فيها مع بعض

  1. Brute force: لكل بداية، عدّ الأصفار والوحايد وسجّل أطول تساوي. O(n²).
  2. الـ transform: لو الـ 0 بقى -1، "عدد الأصفار = عدد الوحايد" معناها "المجموع = 0"، لأن كل 1 بيلغي -1.
  3. إمتى مجموع = 0؟ لما نفس الـ sum يتكرر: الجزء اللي بين المرتين مجموعه صفر.
  4. أطول: عايزين البداية أبعد حاجة لورا، يعني أول ظهور للـ sum، ومش بنحدّثه أبدًا.
  5. Edge cases: الـ array كلها متوازنة (محتاجة الـ -1)، مفيش جزء متوازن (0)، و sum بيتكرر كذا مرة.
  1. الـ map: sum ← أول index. الـ -1 معناها إن الـ sum كان 0 قبل أول عنصر، فلو الجزء المتوازن بيبدأ من 0 ويخلص عند i، طوله i - (-1) = i + 1 من غير edge case.
  2. loop بـ index مش for...of، لأننا محتاجين الـ index نحسب بيه الطول.
  3. الـ transform on the fly، من غير ما نعدّل الـ array نفسها.
  4. ليه i - j مش i - j + 1؟ الجزء بيبدأ من j + 1، لأن j آخر عنصر قبله. جرّب: j = -1 و i = 1 يدّي 2، صح.
  5. ليه الـ set في الـ else بس؟ لو حدّثت كل مرة، هتقيس من بداية أقرب فالطول يقصر: [0, 1, 0, 1] هتطلع 2 بدل 4.
Inputالمتوقعليه الحالة دي مهمة
[0, 1]2الـ array كلها: محتاجة {0: -1}
[0, 0, 0]0مفيش جزء متوازن
[0, 1, 0, 1]4لو حدّثت أول index هتطلع 2
[1, 0, 1, 1, 0, 0]6الـ sum بيرجع للصفر في الآخر بس

التعقيد: O(n) وقت و memory. ولو عايز تستغنى عن الـ Map: الـ sum دايمًا بين -n و n، فـ array طولها 2n + 1 مع offset n تنفع، وأسرع شوية.

الـ pattern العام "عدد" ← map فيها count وتبدأ {0: 1}. "أطول" ← map فيها أول index وتبدأ {0: -1}. ولو "أطول subarray مجموعه k"، نفس الكود ده بس اسأل عن sum - k.

لحد دلوقتي بندوّر على مجموع بالظبط. طب لو الشرط إن المجموع يقبل القسمة على k؟

مثال محلول 6: Subarray Sums Divisible by K

Subarray Sums Divisible by K

mediumLeetCode 974

عدّ الـ subarrays المتصلة (غير الفاضية) اللي مجموعها بيقبل القسمة على k. الأرقام ممكن تبقى سالبة، و k موجب.

Input: nums = [4, -7, 2, 5, -3], k = 5 → 3 ([-7, 2] = -5, [-7, 2, 5] = 0, [5] = 5) Input: nums = [1, 2], k = 7 → 0

الجديد هنا إن الـ key في الـ map بقى الباقي مش الـ sum، وده بيجيب معاه فخ الـ % السالب في JS.

نفكّر فيها مع بعض

  1. Brute force: كل subarray ومجموعه الجاري، O(n²).
  2. الـ key insight: prefix[j] - prefix[i] بيقبل القسمة على k ⟺ الاتنين ليهم نفس الباقي. مثال: 17 و 2 باقيهم 2 على 5، والفرق 15.
  3. الخطة: نفس قالب 560 بالظبط، بس نعدّ prefixes بنفس الباقي. والبواقي من 0 لـ k - 1، فـ array طولها k تكفي، و count[0] = 1 هو الـ empty prefix.
  4. الفخ: في JS -3 % 5 = -3 مش 2، مع إن الاتنين نفس الباقي. لازم normalize.
  1. بعد الـ normalize البواقي من 0 لـ k - 1، فـ array طولها k كفاية وأسرع من Map، والـ index هو الباقي.
  2. نفس {0: 1}: من غيره [5] مع k = 5 مش هتتعد.
  3. الـ sum في حدود المسألة أقصاه حوالي 3 × 10⁸، بعيد جدًا عن 2⁵³.
  4. أهم سطر. الـ % في JS بياخد إشارة sum، فـ count[-3] = undefined والنتيجة NaN. أول % بيجيبه بين -(k-1) و k-1، والـ + k بيخليه موجب، وتاني % بيرجّعه تحت k.
  5. كل prefix قديم بنفس الباقي = subarray مجموعه بيقبل القسمة، زي seen.get(need) في 560.
  6. نسجّل بعد العدّ، لنفس سبب 560.

الصف التاني count، والـ index فوق كل خانة هو الباقي. ركّز على الـ sum السالب:

Inputالمتوقعليه الحالة دي مهمة
[4, -7, 2, 5, -3], k = 53بالـ % الخام (مع Map) هتطلع 1
[5], k = 51محتاجة count[0] = 1
[0, 0], k = 33كل subarray مجموعه 0، والـ 0 بيقبل القسمة
[1, 2], k = 70مفيش ولا واحد

التعقيد: O(n) وقت و O(k) memory.

كده الأفكار كلها خلصت. إيه الغلطات اللي بتوقّع الناس في كل اللي فات؟

غلطات مشهورة

كلها بتطلّع Wrong Answer أو NaN من غير أي error، وده اللي بيخلّيها صعبة تتلاقي.

1. prefix طوله n، و l = 0 بيطلّع NaN

الحل: prefix طوله n + 1 و prefix[r + 1] - prefix[l]. أأمن من إنك تفتكر (l > 0 ? pre[l - 1] : 0) كل مرة.

2. نسيت {0: 1}

الحل: new Map([[0, 1]]). ونفس الفكرة بشكلين تانيين: {0: -1} في "أطول"، و count[0] = 1 في البواقي.

3. سجّلت الـ sum قبل ما تعدّ

الحل: اسأل الأول، وبعدين سجّل. الـ map لازم يبقى فيها اللي قبل العنصر الحالي بس.

4. Set بدل count

الحل: Map فيها count، و count += seen.get(need) || 0.

5. الـ % السالب في JS

الحل: ((sum % k) + k) % k. هتقابلها في أي مسألة فيها باقي وأرقام سالبة. (C++ و Java نفس المشكلة، و Python بترجّع موجب لوحدها.)

6. حدّثت أول index في مسائل "أطول"

الحل: set جوه else بس. "أطول" = أبعد بداية = أول ظهور.

عارف الغلطات. تقدر تتجنبها وإنت بتجاوب؟

اختبر نفسك

في Subarray Sum Equals K، ليه الـ map بتبدأ بـ {0: 1}؟

  • عشان الـ map ما تبقاش فاضية وتضرب error
  • عشان الـ 0 هو الـ empty prefix، ومن غيره الـ subarrays اللي بتبدأ من index 0 مش هتتعد
  • عشان k ممكن يبقى 0
  • مش ضروري، الحل بيشتغل من غيره

subarray بيبدأ من 0 مجموعه prefix[j+1] - prefix[0]، فمحتاج prefix[0] = 0 يبقى في الـ map. وموضوع k = 0 بيتحل بترتيب السطور، مش بالـ {0: 1}.

في JS، -7 % 3 بيساوي كام؟ وبعد ((-7 % 3) + 3) % 3؟

  • 2 و 2
  • -1 و 2
  • -1 و -1
  • 1 و 1

JS بتاخد إشارة الرقم اللي بيتقسم: -7 = 3 × (-2) + (-1). والـ normalize: (-1 + 3) % 3 = 2، وده الصح رياضيًا: -7 = 3 × (-3) + 2.

مسألة فيها نوعين من العمليات بالتبادل: "غيّر nums[i]" و "مجموع l..r كام؟". الـ prefix sum العادي ينفع؟

  • أيوه، كل حاجة O(1)
  • أيوه، بس الـ query تبقى O(log n)
  • مش كويس: كل update بيعدّل كل الـ prefix اللي بعده، O(n). الحل Fenwick أو segment tree
  • لأ، لازم brute force

لو غيّرت nums[2]، كل prefix[3..n] لازم تتغيّر. الـ prefix sum بيلمع لما الـ array immutable، زي ما اسم 303 بيقول.

في Contiguous Array، ليه بنخزّن أول index لكل sum وما بنحدّثهوش؟

  • عشان الـ Map ما تكبرش
  • عشان أول ظهور = أبعد بداية = أطول subarray
  • عشان الـ index الأخير ممكن يبقى -1
  • مش فارقة، الاتنين هيدّوا نفس الإجابة

الطول i - j، فكل ما j يصغر، الطول يكبر. لو حدّثت، [0, 1, 0, 1] هتطلع 2 بدل 4.

array فيها سالب، والمطلوب طول أطول subarray مجموعه k. أحسن أداة؟

  • Sliding window
  • Prefix + map فيها count، وتبدأ {0: 1}
  • Prefix + map فيها أول index، وتبدأ {0: -1}، وتسأل عن sum - k
  • Sort وبعدين two pointers

السالب بيقفل الـ window. و"أطول" يعني أول index زي 525، بس بتسأل عن sum - k. والـ sort بيبوّظ الـ "متصل".

تمرين: فكّر قبل ما تفتح

Count Number of Nice Subarrays

mediumLeetCode 1248

عدّ الـ subarrays المتصلة اللي فيها بالظبط k أرقام فردية.

nums = [2, 1, 1, 2, 1], k = 2 → 5 nums = [2, 4, 6], k = 1 → 0
تلميح 1

الأرقام نفسها مش مهمة، المهم فردي ولا زوجي. اعمل transform: الفردي 1 والزوجي 0، زي ما عملنا في Contiguous Array.

تلميح 2

بعد الـ transform، عدد الفرديات في أي subarray = مجموعه. يعني دي Subarray Sum Equals K بالحرف: نفس الـ map، ونفس {0: 1}، ونفس الترتيب.

الحل

x % 2 === 1 شغالة هنا لأن الأرقام موجبة. لو ممكن تبقى سالبة، -3 % 2 = -1 (نفس فخ الـ modulo)، فاكتب x % 2 !== 0.

لو جاوبت كله صح، إنت جاهز. تتمرن على أنهي مسائل، وبأنهي ترتيب؟

اتمرن على LeetCode بالترتيب

حلها بالترتيب ده، كل مسألة بتزوّد فكرة واحدة. لو قعدت أكتر من 25 دقيقة على مسألة، ارجع للقالب بتاعها هنا، وبعدين حاول تاني من غير ما تبص.

عايز الفصل كله في صفحة واحدة تراجع منها قبل الانترفيو؟

الخلاصة

في جملة واحدة أي جزء متصل = فرق بين اتنين prefix. لو بتسأل عن range معيّن، اطرح. ولو بتعدّ أو بتدوّر، خزّن الـ prefixes اللي فاتت في map، واسأل عن اللي محتاجه قبل ما تسجّل اللي معاك.
السؤالالإجابة
طول الـ prefix؟n + 1، و prefix[0] = 0.
مجموع l..r؟prefix[r + 1] - prefix[l]. لو المسألة بتعدّ من 1، حوّل لـ 0 الأول.
الـ map بتبدأ بإيه؟{0: 1} للعدّ، {0: -1} للأطول، count[0] = 1 للبواقي.
أسأل ولا أسجّل الأول؟اسأل الأول، وإلا هتعدّ subarray فاضي.
count ولا أول index؟"كام" ← count. "أطول" ← أول index وما تحدّثوش.
الباقي السالب؟((x % k) + k) % k.
Sliding window ولا prefix؟كله موجب وعايز أطول أو أقصر: window. فيه سالب أو عايز مجموع بالظبط: prefix + map.
Complexity؟O(n) وقت، O(n) memory، و O(1) لكل query.

الفصل الجاي: Sorting و Intervals. هناك الـ prefix sum متخبّي في مسائل الـ intervals: كل meeting بتبدأ تحط +1 وكل واحدة بتخلص تحط -1، وبعد ما ترتّب الأحداث بالوقت، الـ running sum هو عدد الـ meetings الشغالة في أي لحظة. ده اسمه sweep line، وأساسه الجمع الجاري اللي اتعلمته هنا. بس الأول لازم تعرف الـ sort بيشتغل إزاي، وده أول حاجة هناك.