Hash Map و Sethash map · set · counting · complement · grouping

بدل ما تلف على الـ array كلها عشان تعرف "شفت الحاجة دي قبل كده؟"، بتسجّل اللي شفته في hash map وتسأله في O(1) on average. بتدفع شوية memory، والـ O(n²) بيبقى O(n).

قبله: Arrays و Strings و Big-O بيمهّد لـ: Two Pointers و Sliding Window و Prefix Sum

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

  • الـ hash map شغال إزاي من جوه: hash function و buckets و collisions، وليه هو O(1) on average و O(n) في الـ worst case.
  • تختار صح بين Map و Set و object في JS، وتعرف فخاخ الـ object.
  • الخمس patterns: counting، و complement، و grouping، و seen-set، و value → index، وتكتبهم من دماغك.
  • تحل Two Sum و Valid Anagram و Group Anagrams و Top K Frequent و Longest Consecutive، وتشرح الـ complexity في انترفيو.

ليه Hash Map؟

في الفصل اللي فات (Arrays و Strings) شفت إن الـ array بتوصّلك لأي index في O(1). بس لو السؤال "القيمة دي موجودة؟"، لازم تلف عليها كلها. دلوقتي هنحل المشكلة دي بالظبط.

خد أبسط مثال: array أرقام، فيها رقم متكرر؟ الـ brute force: كل رقم قارنه بكل اللي بعده.

ده O(n²): على n = 100,000 حوالي 5 مليار مقارنة، يعني TLE. والسبب إن الـ array مش بتفتكر هي شافت إيه، فكل سؤال بيدوّر من الأول:

تشبيه مدرّس معاه كشكول غياب، وحد سأله: "مازن حضر؟". لو الأسامي مكتوبة ورا بعض من غير نظام، هيقرا الكشكول كله. بس هو عامل صفحة لكل حرف، فيفتح صفحة الميم على طول ويبص في الكام اسم اللي فيها. الصفحة دي bucket، وقاعدة "روح لصفحة أول حرف" هي الـ hash function، ولما مازن ومنى يتكتبوا في نفس الصفحة، ده collision.

الـ hash set بيعمل كده بالظبط: كل رقم تشوفه تسجّله، وتسأل has في خطوة واحدة on average:

8 خطوات بدل 18، وعلى 100,000 عنصر 100,000 خطوة بدل 5 مليار. التمن: الـ Set بياخد O(n) memory، والـ brute force كان O(1). ده الـ trade-off بتاع الفصل كله: memory مقابل وقت.

الفكرة اللي لازم تفضل معاك أي loop داخلية وظيفتها بس إنها تدوّر على حاجة شفتها قبل كده، غالبًا تتشال ويحل محلها has واحد على hash map.

طب إزاي تعرف من نص المسألة إنها محتاجة hash map؟ ده الجزء الجاي.

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

الـ hash map بيدخل في نص المسائل تقريبًا، بس الكلمات دي بتقولك إنه هو الحل الأساسي:

لما تشوف: unsorted arrayreturn indicespair with sumduplicate count / frequencyanagramgroup bytop k / most frequent first uniqueseen beforeO(n) required
ومش هو غالبًا لو: sorted + O(1) extra spaceneed the min / max again and againkeys must stay sorted

لو الـ array مترتبة ومطلوب O(1) memory، two pointers غالبًا أحسن لأنه بيستغل الترتيب. ولو محتاج الـ min أو الـ max كل شوية، ده heap. والـ Map في JS بيحفظ ترتيب الإضافة بس، مش بيرتّب الـ keys.

الـ patternالسؤال اللي بتسألهبتخزّن إيهأشهر مسائل
العدّ
counting
كل حاجة اتكررت كام مرة؟Map: value → count، أو array 26 للحروفValid Anagram، Top K Frequent، First Unique Character
المكمّل
complement
شفت الرقم اللي يكمّلني؟Map: value → indexTwo Sum، وبعدين Subarray Sum Equals K في prefix sum
التجميع
grouping
مين شبه مين؟Map: key → listGroup Anagrams
الـ seen-set
seen set
الحاجة دي ظهرت قبل كده؟SetContains Duplicate، Longest Consecutive، Happy Number
value → index
last / first position
الرقم ده كان فين آخر مرة؟Map: value → indexContains Duplicate II، وأطول substring في sliding window
flowchart TD
  A["What must I remember about each element?"] --> B{"Only whether it appeared?"}
  B -- yes --> S["Set"]
  B -- no --> C{"How many times it appeared?"}
  C -- yes --> F["Map value to count, or an array of 26 for a-z"]
  C -- no --> D{"Where it appeared?"}
  D -- yes --> I["Map value to index"]
  D -- no --> G{"Which elements belong together?"}
  G -- yes --> K["Map key to list"]
  

السؤال اللي بيحدد كل حاجة: "محتاج أفتكر إيه عن كل عنصر عدّيت عليه؟".

طب الـ Map ده بيرد في O(1) إزاي أصلًا؟ تعالى نفتحه من جوه.

الـ hash map من جوه

جوه أي Map أو Set فيه array عادية اسمها buckets، والـ array بتوصّلك لأي index في O(1). الـ key insight كله: نحوّل الـ key (اسم، رقم، أي حاجة) لـ index.

  1. hash function: تحوّل الـ key لرقم. أهم شرط: نفس الـ key يطلّع نفس الرقم كل مرة، وإلا مش هتلاقي اللي خزّنته.
  2. % size: عشان الرقم يبقى index صالح من 0 لـ size - 1.
  3. jump: تروح للـ bucket ده على طول، من غير ما تلمس الباقي. ودي الـ O(1).
  4. collision: اتنين keys ممكن يطلعوا نفس الـ index، فكل bucket بيبقى list صغيرة اسمها chain، بتقارن فيها واحد واحد.

ده hash map حقيقي شغال، بـ hash function بسيطة عشان تقدر تحسبها في دماغك:

  1. 7 buckets، كل واحد array فاضية. الـ () => [] بتدّي كل bucket array جديدة، لكن fill([]) هيخلّي الـ 7 يشاوروا على array واحدة.
  2. بنجمع الـ char codes. دي hash function ضعيفة عن قصد، وهتشوف عيبها بعد شوية.
  3. أي رقم % 7 بيطلع من 0 لـ 6، فالـ index صالح دايمًا. وبنقسم على this.buckets.length مش رقم ثابت، عشان لو العدد اتغيّر ما نطلعش برا الـ array.
  4. قلب الـ O(1): رحنا لـ bucket واحد بس، والباقي ما اتلمسش.
  5. لو الـ key موجود، نغيّر القيمة ونعمل early return، عشان كده الـ Map عمره ما بيخزّن نفس الـ key مرتين. والـ loop دي هي تمن الـ collisions.
  6. key جديد: نضيفه في آخر الـ chain.
  7. الـ get بيمشي نفس الطريق بالظبط، وده سبب إن الـ hash لازم يبقى ثابت.
  8. الـ missing key بيرجّع undefined زي Map.get، وده سبب إن map.get(x) + 1 بيطلع NaN أول مرة.

شوفه وهو بيخزّن

كل صف bucket، والرقم على الشمال هو الـ index. الخانات جنب بعض هي الـ chain، والخانة الباهتة bucket فاضي:

'nour' وقعت في bucket 'omar'، فالـ get قارن بـ 'omar' الأول. ده كل تمن الـ collision هنا: مقارنة زيادة.

ليه O(1) on average و O(n) في الـ worst case؟

لو عندك n key و m bucket والتوزيع كويس، كل chain فيها حوالي n / m، والرقم ده اسمه load factor. الـ Map الحقيقي لما الـ load factor يعدّي حد معين (حوالي 0.75 في لغات كتير) بيعمل resize: buckets الضعف، وكل key يتحط في مكانه الجديد. فالـ chains بتفضل قصيرة والعملية O(1). الـ resize نفسه O(n)، بس بيحصل كل ما العدد يتضاعف، فلو وزّعته على الـ inserts يبقى amortized O(1)، زي push في الـ array.

الـ worst case: كل الـ keys في bucket واحد، فالـ chain طولها n وكل get بقى O(n). والـ hash بتاعتنا بتعمل كده فعلًا، لأنها بتجمع الحروف من غير ما ترتيبها يفرق. يعني أي كلمتين نفس الحروف هيقعوا في نفس الـ bucket:

5 inserts و get واحد عملوا 15 مقارنة، ومع n key هيبقوا حوالي n²/2. الحل في الـ hash function: لازم مكان الحرف يفرق.

الضرب في 31 بيخلّي كل حرف يتضرب حسب مكانه، فـ eat و tea يطلعوا مختلفين. دي تقريبًا طريقة Java في String.hashCode. والـ Map في JS جواه hash function أقوى من دي، وبيعمل resize لوحده.

العمليةon averageworst caseملاحظة
set / addO(1)O(n)amortized، بسبب الـ resize
get / hasO(1)O(n)الـ worst لما كل الـ keys في bucket واحد
deleteO(1)O(n)
تلف على كل العناصرO(n)O(n)في JS بترتيب الإضافة
الـ memoryO(n)O(n)ده التمن

ولو الـ key string طوله k، حساب الـ hash نفسه O(k). غالبًا بنعتبره ثابت، بس في Group Anagrams تحت الـ k هتدخل في الحساب.

في الانترفيو قول "O(1) average". ولو اتسألت عن الـ worst case: "O(n) لو كل الـ keys وقعت في bucket واحد، وده نادر مع hash function كويسة". الجملة دي بتبيّن إنك فاهم اللي جوه، مش حافظ.

الـ HashMap بتاعنا فيه 7 buckets ومن غير resize. حطّينا فيه 7000 key متوزعين كويس جدًا. get هيقارن حوالي كام key؟

  • 1، لأن الـ hash map دايمًا O(1)
  • 7
  • حوالي 1000
  • 7000

7000 على 7 يعني كل chain حوالي 1000. الـ O(1) جاية من الـ resize اللي بيخلّي الـ load factor صغير، ومن غيره العملية O(n / m).

فهمنا اللي جوه. طب في JS تستخدم Map ولا Set ولا object عادي؟

Map و Set و object في JS

الـ default بتاعك: Map لما تحتاج key → value، و Set لما تحتاج "موجود ولا لأ" بس. ده كل الـ API اللي هتحتاجه:

MapSetobject {}
بيخزّنkey → valuevalues بسkey → value
نوع الـ keyأي حاجة، والرقم بيفضل رقمأي حاجةstring بس: o[1] و o['1'] نفس الـ key
العددm.size في O(1)s.sizeObject.keys(o).length، وده O(n)
keys موروثةلألأأيوه: constructor و toString موجودين من الأول
الترتيبترتيب الإضافةترتيب الإضافةالـ keys اللي شكلها أرقام الأول، وبعدها الباقي
امتىالعدّ والـ lookup: الـ default"شفته قبل كده؟"keys ثابتة ومعروفة، أو JSON

أخطر فرق هو نوع الـ key: الـ object بيحوّل أي key لـ string.

والـ Map والـ Set بيقارنوا الأرقام والـ strings بالقيمة، لكن الـ arrays والـ objects بالـ reference: "هي نفس الـ array دي في الـ memory؟"، مش "شكلها زيها؟".

عشان كده الـ composite key بتعمله string: `${r},${c}`. هتستخدمها كتير في الـ grids.

|| 0 ولا ?? 0؟ في العدّ (map.get(x) || 0) + 1 و ?? 0 الاتنين صح. بس لو القيمة المتخزّنة ممكن تبقى 0 وليها معنى (زي index 0)، الـ || هيمسحها، فاستخدم ?? أو has.

ولو الـ keys حروف a لـ z بس، array من 26 خانة أسرع من أي Map: مفيش hash ولا collisions، والـ index هو ch.charCodeAt(0) - 97، زي ما شفت في Arrays و Strings.

عرفنا الأدوات. طب بنستخدمها في أنهي أشكال؟ خمس patterns بيغطّوا تقريبًا كل حاجة.

الخمس patterns

كل مسائل الـ hashing تقريبًا واحد من الخمسة دول، أو اتنين مع بعض:

  1. Counting. أول مرة freq.get(x) بترجّع undefined، والـ || 0 بتخليها 0. من غيرها هتطلع NaN وتفضل NaN من غير ولا error.
  2. Complement. Map مش Set عشان المسألة غالبًا عايزة مكان الشريك. لو المطلوب true/false بس، Set يكفي.
  3. a + b = target يعني b = target - a. فبدل ما تدوّر على أي شريك، بتسأل عن رقم واحد بالظبط، وده اللي بيشيل الـ loop الداخلية.
  4. بنسجّل بعد السؤال. لو العكس، arr[i] = 3 مع target = 6 هيلاقي نفسه ويرجّع [i, i].
  5. Grouping. الشغل كله في الـ key: واحد لكل اللي يتجمعوا، ومختلف لأي اتنين ما يتجمعوش. وما تكتبش groups.set(key, list.push(x))، لأن push بترجّع الطول مش الـ array.
  6. Seen-set. اسأل الأول وبعدين ضيف، فالـ loop بتعمل early return أول ما تلاقي التكرار. الـ one-liner new Set(arr).size !== arr.length صح، بس بيبني الـ Set كله دايمًا.
  7. Value → index. الـ set بيكتب فوق القديم، فالـ Map شايل آخر مكان. ولو عايز أول مكان: if (!first.has(x)) first.set(x, i). هتحتاج الاتنين في sliding window و prefix sum.

أول pattern وهو بيعدّ حروف "banana":

يلا نطبّق. أول مثال هو أشهر مسألة في LeetCode كله: Two Sum.

مثال محلول 1: Two Sum

Two Sum

easyLeetCode 1

array أرقام مش مترتبة ورقم target. رجّع الـ indices بتوع عنصرين في مكانين مختلفين مجموعهم target. مضمون إن فيه إجابة واحدة بالظبط.

Input: nums = [4, 9, 6, 1, 13, 5], target = 11 Output: [2, 5] (6 + 5 = 11) Input: nums = [3, 3], target = 6 Output: [0, 1] (same value, two different positions)

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

  1. افهم المطلوب: indices مش قيم، والـ array مش مترتبة. ما ينفعش العنصر يتستخدم مرتين، بس [3, 3] ينفع لأنهم مكانين.
  2. Brute force: كل زوج، O(n²) وقت و O(1) memory. قوله كبداية.
  3. Sort + two pointers؟ الـ sort بيضيّع الـ indices الأصلية، إلا لو رتّبت أزواج [value, index]، وده O(n log n).
  4. الـ key insight: عند nums[i] إنت عارف الشريك: target - nums[i]. فالسؤال بقى "شفته قبل كده؟ وفين؟". الجديد هنا إن الـ Map مش بيفتكر "شفته" وبس، بيفتكر "شفته فين".
  5. ليه one pass كفاية؟ لو الإجابة [j, i] و j < i، فـ nums[j] اتسجّل قبل ما نوصل لـ i. كل زوج بيتلقط عند عنصره التاني.
  6. Edge cases: [3, 3]، وعنصر شريكه هو نفسه زي [3, 2, 4] مع 6، وسالب وصفر، و index 0.
  1. value → index. Set مش هينفع لأن المطلوب الـ index، والـ object هيحوّل الأرقام لـ strings من غير ما تحس.
  2. i < nums.length مش <=: آخر index هو length - 1، و nums[length] هتبقى undefined والـ need هيبقى NaN.
  3. الشريك المطلوب بالظبط. ده اللي بيحوّل "دوّر على أي حد يكمّلني" لـ lookup واحد في O(1).
  4. has مش get: لو الشريك في index 0، get هترجّع 0 وده falsy، فهتفوّت الإجابة. والـ index القديم الأول لأنه الأصغر.
  5. بعد السؤال. لو بدّلت السطرين، [3, 2, 4] مع 6 هترجّع [0, 0].
  6. مش هيتنفّذ لأن الإجابة مضمونة، بس الدالة لازم ترجّع حاجة في كل path.

على [4, 9, 6, 1, 13, 5] و target = 11:

Inputالمتوقعليه الحالة دي مهمة
[3, 3], 6[0, 1]نفس القيمة في مكانين: السؤال قبل التسجيل بيخليها تشتغل
[3, 2, 4], 6[1, 2]لو سجّلت قبل ما تسأل: [0, 0]
[-3, 4, 3, 90], 0[0, 2]سالب: need = 0 - (-3) = 3
[0, 4, 3, 0], 0[0, 3]الشريك في index 0: هنا get بيوقعك

Complexity: one pass، وكل lookup O(1) average، فالوقت O(n) والـ memory O(n). بدّلنا O(1) memory بـ O(n) عشان ننزل من O(n²).

في الانترفيو ابدأ بالـ brute force، وبعدين قول: "أقدر أبدّل memory بوقت، لأني عارف شريك كل رقم". ولو الـ interviewer قال "الـ array مترتبة"، ده hint لـ two pointers بـ O(1) memory.

هنا الـ Map كان شايل index. طب لو المهم مش "فين" لكن "كام مرة"؟

مثال محلول 2: Valid Anagram

Valid Anagram

easyLeetCode 242

string s و string t فيهم حروف إنجليزي صغيرة بس. هل t هي حروف s بعد ما تتلخبط؟ يعني نفس الحروف، وكل حرف بنفس العدد.

Input: s = "listen", t = "silent" → true Input: s = "apple", t = "paple" → true Input: s = "aab", t = "abb" → false (same letters, different counts)

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

  1. افهم المطلوب: الترتيب مش مهم، المهم عدد كل حرف. "aab" و "abb" نفس الحروف بأعداد مختلفة: false.
  2. أول حل: sort الاتنين وقارن. سطر واحد، بس O(n log n).
  3. الجديد هنا إن الـ map بيعدّ بدل ما يفتكر مكان: عدّ حروف s وحروف t وقارن، في O(n).
  4. Map ولا array 26؟ الحروف a لـ z بس، فـ array 26 أسرع (مفيش hash خالص)، والـ memory ثابتة O(1) مهما الـ string طوّل.
  5. array واحدة كفاية: ++ لحروف s و -- لحروف t. لو أي عداد نزل تحت الصفر، t فيها زيادة، فنعمل early return.
  6. Edge cases: أطوال مختلفة، أعداد مختلفة، strings فاضية.
  1. ده جزء من صحة الحل، مش optimization. من غيره s = "ab" و t = "a" هترجّع true: الـ check التحت بيلقط الزيادة في t بس، والطول هو اللي بيلقط النقص.
  2. من غير fill(0) هتبقى undefined++ يعني NaN. و fill(0) آمنة لأن الصفر primitive، مش array.
  3. charCodeAt(i) - 97 بيحوّل 'a'..'z' لـ 0..25 على طول. و < لأن آخر index هو length - 1.
  4. نفس الحساب بالسالب. لو العداد نزل تحت الصفر، t استخدمت الحرف ده أكتر من s: early return.
  5. مش محتاجين نلف نتأكد إن كله صفر: مجموع العدادات = الطولين ناقص بعض = صفر، ومفيش سالب، يبقى كلهم صفر.

الـ 26 خانة بتتملا من "listen" وتفضى بـ "silent". صف الحروف هو اسم الخانة، واللي تحته العداد:

ولو الحروف ممكن تبقى أي حاجة، نفس الفكرة بـ Map:

هنا !count.get(ch) مقصودة: undefined (مش موجود) و 0 (خلص) الاتنين معناهم زيادة في t. يعني هنا الـ falsy بتاعة الصفر في صالحنا، عكس Two Sum.

الطريقةالوقتالـ memoryامتى
sort وقارنO(n log n)O(n)أسرع حاجة تكتبها، كبداية
array 26O(n)O(1)a لـ z بس: الأحسن
MapO(n)O(k)، k = عدد الحروف المختلفةأي حروف: Unicode، أرقام، رموز
Inputالمتوقعليه الحالة دي مهمة
"aab", "abb"falseالعداد بتاع b هينزل لـ −1
"ab", "a"falseمن غير فحص الطول هترجّع true
"", ""trueالـ loops مش هتلف أصلًا
"abc", "cba"trueمقلوب الكلمة anagram ليها
الـ follow-up المشهور "طب لو فيه Unicode، حروف عربي أو emoji؟". روح للـ Map. و for...of بيمشي على الحروف الحقيقية، لكن s[i] و s.length بيعدّوا وحدات UTF-16، والـ emoji بياخد اتنين منهم.

عرفنا نقول إن كلمتين anagram. طب لو عندك 10,000 كلمة وعايز تجمّع كل الـ anagrams مع بعض؟

مثال محلول 3: Group Anagrams

Group Anagrams

mediumLeetCode 49

array كلمات بحروف إنجليزي صغيرة. جمّع كل الكلمات اللي anagrams لبعض في group واحدة. ترتيب الـ groups والكلمات جواها مش مهم.

Input: ["tap", "pat", "dog", "apt", "god", "cat"] Output: [["tap", "pat", "apt"], ["dog", "god"], ["cat"]] (any order)

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

  1. افهم المطلوب: كل group كلمات نفس الحروف بنفس الأعداد، والكلمة اللي مالهاش أصحاب group لوحدها.
  2. Brute force: كل كلمة تتقارن بكل group بـ isAnagram: لحد O(n² · k)، و k طول الكلمة.
  3. الجديد هنا إن الـ count (أو الحروف المترتبة) بقى key: لكل كلمة signature واحد لكل الـ anagrams ومختلف لغيرهم، وبعدين grouping pattern عادي.
  4. Signature 1، الحروف مترتبة: "tap" بتبقى "apt". ده O(k log k) للكلمة، والمجموع O(n · k log k).
  5. Signature 2، عدد كل حرف: array 26 تتحوّل string. ده O(k) للكلمة، والمجموع O(n · k).
  6. Edge cases: "" (الـ key string فاضي، عادي جدًا)، كلمة واحدة، و "ab" مع "abb".
  1. الـ object غالبًا هيشتغل هنا، بس الـ Map هو العادة الآمنة: مفيش keys موروثة، و .values() جاهزة تحت.
  2. sort() من غير comparator صح هنا: الـ default بيرتّب كـ strings، وإحنا فعلًا بنرتّب حروف.
  3. group فاضية أول مرة. لازم قبل الـ push، وإلا undefined.push هيضرب error.
  4. بنضيف الكلمة الأصلية، مش الـ signature.
  5. values() بترجّع iterator، والـ [...] بتحوّله array.

الـ signature التاني: عدد كل حرف

  1. array جديدة لكل كلمة، وإلا العدادات تتراكم من كلمة للتانية.
  2. نفس العدّ بتاع Valid Anagram، O(k).
  3. ليه '#'؟ من غيرها، a = 1 و b = 11 بيطلع "111..."، و a = 11 و b = 1 بيطلع "111..." برضه. وبنحوّل لـ string أصلًا لأن الـ Map بيقارن الـ arrays بالـ reference.
  4. نفس سطور الـ grouping. اللي اتغيّر بس حساب الـ key، وده الـ pattern كله.

مثلًا الـ signature بتاع "eat" هو 1#0#0#0#1#0#0#0#0#0#0#0#0#0#0#0#0#0#0#1#0#0#0#0#0#0: واحد في خانة a، وواحد في e، وواحد في t.

الـ signatureالـ key بتاع "tap"لكل كلمةالمجموع
الحروف مترتبة"apt"O(k log k)O(n · k log k)
عدد كل حرف"1#0#...#1#...#1#..."O(k + 26)O(n · k)

الـ memory في الاتنين O(n · k). ولو الكلمات قصيرة (LeetCode بيقول لحد 100 حرف)، الفرق في الواقع صغير. قول الاتنين في الانترفيو، لأن ده بيبيّن إن اختيار الـ key هو المسألة كلها.

Inputالمتوقعليه الحالة دي مهمة
[""][[""]]الـ key string فاضي، وده key عادي في الـ Map
["a"][["a"]]كلمة واحدة: group واحدة
["ab", "ba", "abb", "bba", "bab"][["ab", "ba"], ["abb", "bba", "bab"]]نفس الحروف بأعداد مختلفة لازم يتفصلوا

لحد دلوقتي العدد كان value جوه الـ Map. طب لو استخدمناه index؟

مثال محلول 4: Top K Frequent Elements

Top K Frequent Elements

mediumLeetCode 347

array أرقام ورقم k. رجّع الـ k أرقام اللي اتكرروا أكتر حاجة، بأي ترتيب. الإجابة مضمونة إنها واحدة، والمسألة بتطلب حل أحسن من O(n log n).

Input: nums = [5, 7, 5, 3, 7, 5, 9, 7, 5], k = 2 Output: [5, 7] (5 appears 4 times, 7 appears 3 times)

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

  1. أول خطوة: counting pattern، O(n).
  2. بعد العدّ: sort بالعدد وخد أول k: O(n log n). والمسألة عايزة أحسن.
  3. Heap حجمه k: O(n log k)، هتشوفه في Heap.
  4. الجديد هنا إن العدد نفسه بقى index: الـ frequency رقم صحيح من 1 لـ n، فـ buckets[f] فيها الأرقام اللي اتكررت f مرة، ونمشي من فوق لتحت. ده bucket sort من غير ولا مقارنة.
  5. ليه O(n)؟ العدّ O(n)، والـ buckets n + 1 خانة، والتوزيع O(m) (عدد الأرقام المختلفة)، والمشي O(n). كله O(n).
  6. Edge cases: كل الأرقام زي بعض (العدد = n)، و k = عدد الأرقام المختلفة، وأرقام سالبة.
  1. counting pattern زي ما هو.
  2. ليه + 1؟ أكبر عدد ممكن n (زي [2, 2, 2])، فمحتاجين index رقم n، يعني طول n + 1. و () => [] عشان كل bucket array لوحده.
  3. [x, f] destructuring لكل entry، و x بيروح الخانة اللي رقمها عدده. الـ value بقت مكان.
  4. من n لتحت عشان الأكتر تكرارًا الأول. f >= 1 لأن الخانة 0 دايمًا فاضية، و res.length < k بتوقف بدري.
  5. ناخد اللي ناقصنا بس، والـ break بيحمي لو الـ bucket فيه أكتر من المطلوب.
  6. الترتيب مش مهم في المسألة.

التلات مراحل: counting، وبعدين توزيع على الـ buckets، وبعدين المشي من فوق:

الطريقةالوقتالـ memory
counting + sort بالعددO(n log n)O(n)
counting + heap حجمه kO(n log k)O(n + k)
counting + bucket sortO(n)O(n)
Inputالمتوقعليه الحالة دي مهمة
[2, 2, 2], k = 1[2]العدد = n، فلازم الطول n + 1
[8], k = 1[8]عنصر واحد
[-1, -1, 4], k = 1[-1]سالب: العدد هو الـ index، مش الرقم
[1, 2, 3], k = 3[1, 2, 3]كله في bucket واحد
في الانترفيو الـ sort مقبول كأول حل، وبعدين هيسأل "تقدر أحسن؟". قول الـ heap و O(n log k)، وبعدين: "بس العدد عمره ما يعدّي n، فأقدر أستخدمه index وأوصل O(n)". ملاحظة إن القيمة محدودة فتنفع index بتتكرر كتير.

كل اللي فات كان Map. آخر مثال بـ Set بس، وفيه loop جوه loop وبرضه O(n). إزاي؟

مثال محلول 5: Longest Consecutive Sequence

Longest Consecutive Sequence

mediumLeetCode 128

array أرقام مش مترتبة. رجّع طول أطول سلسلة أرقام ورا بعض في العدّ (x، x + 1، x + 2...)، والأرقام ممكن تبقى في أي مكان في الـ array. المطلوب O(n).

Input: [10, 4, 20, 1, 3, 11, 2, 12] Output: 4 (1, 2, 3, 4) Input: [1, 2, 2, 3] Output: 3 (duplicates count once)

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

  1. افهم المطلوب: مش subarray متصل. الـ 1 و 2 و 3 و 4 مبعترين، المهم إن قيمهم ورا بعض.
  2. أول حل: sort وعدّ، O(n log n). والمطلوب O(n).
  3. Set عشان "x + 1 موجود؟" تبقى O(1). بس لو من كل رقم مشيت لفوق، [1..n] هياخد حوالي n²/2.
  4. الجديد هنا إن مش كل رقم يبدأ عدّ: ابدأ بس من بداية السلسلة، يعني x اللي x - 1 بتاعه مش موجود. والـ complexity بتتحسب على البرنامج كله، مش لفة لفة.
  5. ليه O(n)؟ كل سلسلة بتتعدّ مرة واحدة من بدايتها، وكل رقم في سلسلة واحدة. فالـ while على البرنامج كله بتعدّي على كل رقم مرة بالكتير: حوالي 2n عملية.
  6. Edge cases: array فاضية، تكرار، أرقام سالبة.
  1. بناء الـ Set O(n)، وبيشيل الـ duplicates لوحده.
  2. 0 مش 1، عشان الـ array الفاضية إجابتها 0.
  3. على الـ Set مش nums. لو الـ 1 متكرر 5000 مرة في nums، كل نسخة هتبقى "بداية" وتعيد نفس المشي.
  4. قلب الحل: لو x - 1 موجود، x هيتعدّ من بداية سلسلته، فنفوّته.
  5. len بيعدّ الطول، وفي نفس الوقت بيحدد الرقم الجاي x + len.
  6. نحدّث الـ best بعد ما السلسلة تخلص.

صفّين: الـ Set بترتيب الـ loop، وتحته نفس الأرقام مترتبة لعينك بس (الكود مش بيرتّب). راقب while steps: عمره ما بيعدّي عدد الأرقام.

Inputالمتوقعليه الحالة دي مهمة
[]0الـ loop مش هتلف، و best يفضل 0
[7]1رقم واحد سلسلة طولها 1
[1, 2, 2, 3]3التكرار ما بيطوّلش السلسلة
[-1, 0, 1, 5]3السالب والصفر عاديين

Complexity: بناء الـ Set O(n)، و has(x - 1) مرة لكل رقم، والـ while على بعضها O(n). المجموع O(n) وقت و memory.

طريقة التفكير دي هتتكرر لما تشوف loop جوه loop، ما تحكمش إنها O(n²) على طول. اسأل: "الـ loop الداخلية، على البرنامج كله، بتعدّي على كل عنصر كام مرة؟". نفس الحساب ده هيثبت إن sliding window O(n).

الحلول دي شغالة. بس فيه غلطات صغيرة بتطلّع Wrong Answer من غير ولا error.

غلطات مشهورة

ولا غلطة فيهم بتطلّع error. الكود بيشتغل وبيطلّع إجابة غلط، وده أسوأ نوع bugs.

1. object كـ counter، وكلمة اسمها constructor

أي {} بيورث constructor و toString، فـ counts['constructor'] أول مرة function مش undefined. الحل: new Map()، أو Object.create(null) لو مصمم على object.

2. get بدل has لما القيمة ممكن تبقى 0

0 و '' و NaN كلهم falsy. لو السؤال "موجود؟"، اسأل has.

3. map.get(x) + 1 أول مرة

الصح: (freq.get(x) || 0) + 1، والأقواس مهمة. من غيرها get(x) || 0 + 1 معناها get(x) || 1، لأن الـ + بيتحسب قبل الـ ||، فالعداد يفضل 1.

4. fill([]) للـ buckets

fill بيحط نفس الـ reference في كل خانة. الصح: Array.from({ length: 4 }, () => [])، والـ function بتتنادى لكل خانة فبتعمل array جديدة.

5. array كـ key

الصح: visited.add(`${r},${c}`). والفاصل مهم: من غيره (1, 12) و (11, 2) الاتنين "112"، نفس مشكلة الـ '#' في Group Anagrams.

6. Longest Consecutive وإنت بتلف على nums

على الـ input ده الـ while بتلف 25,000,000 مرة، ونسخة الـ Set بتلف 5,000 بس (جرّبتهم الاتنين). الـ O(n) قايم على إن كل بداية بتتعدّ مرة واحدة، والتكرار بيكسر ده.

عرفت الحلول والفخاخ. جاهز تختبر نفسك؟

اختبر نفسك

في Two Sum، لو كتبنا seen.set(nums[i], i) قبل seen.has(need)، إيه اللي هيحصل مع nums = [3, 2, 4] و target = 6؟

  • نفس الإجابة [1, 2]
  • هترجّع [0, 0]
  • infinite loop
  • error

عند i = 0 هنسجّل 3 → 0، وبعدين need = 3 هيلاقي العنصر نفسه. السؤال قبل التسجيل بيضمن إن الـ Map فيه اللي قبل i بس.

في Group Anagrams بـ signature العدّ، لو كتبت count.join('') من غير '#'، إيه المشكلة؟

  • مفيش مشكلة، بس أبطأ شوية
  • الـ Map مش هيقبل الـ key
  • كلمتين مش anagrams ممكن يطلعلهم نفس الـ signature ويتجمعوا غلط
  • كل كلمة هتبقى في group لوحدها

العدادات اللي فيها أكتر من digit بتلزق: a = 1 و b = 11 وكمان a = 11 و b = 1 الاتنين "111...". الفاصل بيدّي كل عداد حدود واضحة.

في Longest Consecutive فيه while جوه for. الـ time complexity كام؟

  • O(n²)، عشان loop جوه loop
  • O(n log n)
  • O(n)
  • O(n · k) و k طول أطول سلسلة

الـ while بتشتغل بس من بداية سلسلة، وكل رقم في سلسلة واحدة، فعلى البرنامج كله بتعدّي على كل رقم مرة بالكتير.

const o = {}; o[1] = 'x'; o['1'] = 'y';. كام key في o؟

  • 2
  • 1
  • 0
  • error

الـ object بيحوّل الـ key لـ string، فالسطر التاني كتب فوق الأول. مع Map كانوا هيبقوا 2.

في Top K Frequent، ليه طول الـ buckets هو nums.length + 1؟

  • عشان الـ indices في JS بتبدأ من 1
  • احتياطي وخلاص، nums.length كانت هتشتغل
  • عشان أكبر عدد ممكن هو n، ومحتاجين خانة رقمها n
  • عشان الخانة 0 للأرقام السالبة

لو كل الأرقام زي بعض العدد = n، والـ index n محتاج طول n + 1. بطول n بس، buckets[n].push هيضرب error.

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

Contains Duplicate II

easyLeetCode 219

array أرقام ورقم k. فيه مكانين مختلفين i و j فيهم نفس الرقم، والمسافة |i - j| أقل من أو تساوي k؟ حاول في O(n).

nums = [4, 6, 2, 4, 9], k = 3 → true (the two 4s are 3 apart) nums = [4, 6, 2, 4, 9], k = 2 → false
تلميح 1

وإنت عند i، محتاج تعرف عن nums[i] مش بس "ظهر قبل كده؟"، لكن "ظهر فين؟". أنهي pattern من الخمسة؟

تلميح 2

value → index. بس لو الرقم ظهر كذا مرة، تحتفظ بأنهي index؟ مين أقرب لأي j جاي، أول ظهور ولا آخر ظهور؟

الحل

آخر index هو الأقرب لأي i جاي، فلو المسافة منه أكبر من k، أي ظهور أقدم أبعد. و <= لأن المسألة قالت "أقل من أو تساوي". والـ has الأول عشان i - undefined بيطلع NaN. O(n) وقت و memory.

لو الأسئلة دي عدّت، يبقى جاهز لـ LeetCode بالترتيب ده.

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

كل مسألة بتضيف فكرة واحدة جديدة. قبل ما تكتب كود، قول لنفسك: "أنهي pattern؟ وهخزّن إيه في الـ map؟". لو قعدت أكتر من 25 دقيقة، ارجع للقالب هنا، وبعدين حاول تاني من غير ما تبص.

وقبل ما تمشي، الفصل كله في صفحة واحدة.

الخلاصة

في جملة واحدة الـ hash map بيخلّيك تفتكر اللي شفته وتسأل عنه في O(1) on average، فبدل loop داخلية بتدوّر، بتسأل سؤال واحد. والسؤال اللي لازم تجاوبه: "محتاج أفتكر إيه عن كل عنصر؟": وجوده (Set)، أو عدده أو مكانه أو مين شبهه (Map).
السؤالالإجابة
Map ولا Set؟محتاج value مع الـ key (عدد، index، list): Map. "موجود؟" بس: Set.
Map ولا object؟Map. الـ object بيحوّل الـ keys لـ strings وفيه keys موروثة زي constructor.
Map ولا array 26؟a لـ z بس: array، أسرع و O(1) memory. غير كده: Map.
has ولا get؟للسؤال "موجود؟" دايمًا has. الـ get بيكدب عليك لو القيمة 0.
composite key؟حوّله string بفاصل: `${a},${b}`، أو الحروف مترتبة، أو count.join('#').
أسجّل امتى؟في الـ complement: بعد السؤال، عشان العنصر ما يلاقيش نفسه.
Complexity؟O(1) average لكل عملية، O(n) worst لو كله في bucket واحد، و O(n) memory.

الـ Map هيفضل معاك: في Sliding Window هيعدّ الحروف جوه الـ window ويفتكر آخر مكان، وفي Prefix Sum هيعدّ المجاميع اللي شفناها بنفس complement بتاع Two Sum بالظبط.

الفصل الجاي: Two Pointers. هنا حلّينا Two Sum بـ O(n) memory لأن الـ array مش مترتبة. طب لو مترتبة، ينفع نحلها من غير ولا byte زيادة؟