Hash Map و Sethash map · set · counting · complement · grouping
بدل ما تلف على الـ array كلها عشان تعرف "شفت الحاجة دي قبل كده؟"، بتسجّل اللي شفته في hash map وتسأله في O(1) on average. بتدفع شوية memory، والـ O(n²) بيبقى O(n).
هتطلع من الفصل ده وإنت عارف
- الـ 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 مش بتفتكر هي شافت إيه، فكل سؤال بيدوّر من الأول:
الـ hash set بيعمل كده بالظبط: كل رقم تشوفه تسجّله، وتسأل has في خطوة واحدة on average:
8 خطوات بدل 18، وعلى 100,000 عنصر 100,000 خطوة بدل 5 مليار. التمن: الـ Set بياخد O(n) memory، والـ brute force كان O(1). ده الـ trade-off بتاع الفصل كله: memory مقابل وقت.
has واحد على hash map.
طب إزاي تعرف من نص المسألة إنها محتاجة hash map؟ ده الجزء الجاي.
إزاي تعرفه من المسألة
الـ hash map بيدخل في نص المسائل تقريبًا، بس الكلمات دي بتقولك إنه هو الحل الأساسي:
لو الـ 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 → index | Two Sum، وبعدين Subarray Sum Equals K في prefix sum |
| التجميع grouping | مين شبه مين؟ | Map: key → list | Group Anagrams |
| الـ seen-set seen set | الحاجة دي ظهرت قبل كده؟ | Set | Contains Duplicate، Longest Consecutive، Happy Number |
| value → index last / first position | الرقم ده كان فين آخر مرة؟ | Map: value → index | Contains 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.
- hash function: تحوّل الـ key لرقم. أهم شرط: نفس الـ key يطلّع نفس الرقم كل مرة، وإلا مش هتلاقي اللي خزّنته.
% size: عشان الرقم يبقى index صالح من0لـsize - 1.- jump: تروح للـ bucket ده على طول، من غير ما تلمس الباقي. ودي الـ O(1).
- collision: اتنين keys ممكن يطلعوا نفس الـ index، فكل bucket بيبقى list صغيرة اسمها chain، بتقارن فيها واحد واحد.
ده hash map حقيقي شغال، بـ hash function بسيطة عشان تقدر تحسبها في دماغك:
- 7 buckets، كل واحد array فاضية. الـ
() => []بتدّي كل bucket array جديدة، لكنfill([])هيخلّي الـ 7 يشاوروا على array واحدة. - بنجمع الـ char codes. دي hash function ضعيفة عن قصد، وهتشوف عيبها بعد شوية.
- أي رقم
% 7بيطلع من 0 لـ 6، فالـ index صالح دايمًا. وبنقسم علىthis.buckets.lengthمش رقم ثابت، عشان لو العدد اتغيّر ما نطلعش برا الـ array. - قلب الـ O(1): رحنا لـ bucket واحد بس، والباقي ما اتلمسش.
- لو الـ key موجود، نغيّر القيمة ونعمل early return، عشان كده الـ Map عمره ما بيخزّن نفس الـ key مرتين. والـ loop دي هي تمن الـ collisions.
- key جديد: نضيفه في آخر الـ chain.
- الـ
getبيمشي نفس الطريق بالظبط، وده سبب إن الـ hash لازم يبقى ثابت. - الـ 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 average | worst case | ملاحظة |
|---|---|---|---|
set / add | O(1) | O(n) | amortized، بسبب الـ resize |
get / has | O(1) | O(n) | الـ worst لما كل الـ keys في bucket واحد |
delete | O(1) | O(n) | |
| تلف على كل العناصر | O(n) | O(n) | في JS بترتيب الإضافة |
| الـ memory | O(n) | O(n) | ده التمن |
ولو الـ key string طوله k، حساب الـ hash نفسه O(k). غالبًا بنعتبره ثابت، بس في Group Anagrams تحت الـ k هتدخل في الحساب.
الـ 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 اللي هتحتاجه:
Map | Set | object {} | |
|---|---|---|---|
| بيخزّن | key → value | values بس | key → value |
| نوع الـ key | أي حاجة، والرقم بيفضل رقم | أي حاجة | string بس: o[1] و o['1'] نفس الـ key |
| العدد | m.size في O(1) | s.size | Object.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 تقريبًا واحد من الخمسة دول، أو اتنين مع بعض:
- Counting. أول مرة
freq.get(x)بترجّعundefined، والـ|| 0بتخليها 0. من غيرها هتطلعNaNوتفضل NaN من غير ولا error. - Complement.
MapمشSetعشان المسألة غالبًا عايزة مكان الشريك. لو المطلوب true/false بس، Set يكفي. a + b = targetيعنيb = target - a. فبدل ما تدوّر على أي شريك، بتسأل عن رقم واحد بالظبط، وده اللي بيشيل الـ loop الداخلية.- بنسجّل بعد السؤال. لو العكس،
arr[i] = 3معtarget = 6هيلاقي نفسه ويرجّع[i, i]. - Grouping. الشغل كله في الـ key: واحد لكل اللي يتجمعوا، ومختلف لأي اتنين ما يتجمعوش. وما تكتبش
groups.set(key, list.push(x))، لأنpushبترجّع الطول مش الـ array. - Seen-set. اسأل الأول وبعدين ضيف، فالـ loop بتعمل early return أول ما تلاقي التكرار. الـ one-liner
new Set(arr).size !== arr.lengthصح، بس بيبني الـ Set كله دايمًا. - Value → index. الـ
setبيكتب فوق القديم، فالـ Map شايل آخر مكان. ولو عايز أول مكان:if (!first.has(x)) first.set(x, i). هتحتاج الاتنين في sliding window و prefix sum.
أول pattern وهو بيعدّ حروف "banana":
يلا نطبّق. أول مثال هو أشهر مسألة في LeetCode كله: Two Sum.
مثال محلول 1: Two Sum
array أرقام مش مترتبة ورقم target. رجّع الـ indices بتوع عنصرين في مكانين مختلفين مجموعهم target. مضمون إن فيه إجابة واحدة بالظبط.
نفكّر فيها مع بعض
- افهم المطلوب: indices مش قيم، والـ array مش مترتبة. ما ينفعش العنصر يتستخدم مرتين، بس
[3, 3]ينفع لأنهم مكانين. - Brute force: كل زوج،
O(n²)وقت وO(1)memory. قوله كبداية. - Sort + two pointers؟ الـ sort بيضيّع الـ indices الأصلية، إلا لو رتّبت أزواج
[value, index]، ودهO(n log n). - الـ key insight: عند
nums[i]إنت عارف الشريك:target - nums[i]. فالسؤال بقى "شفته قبل كده؟ وفين؟". الجديد هنا إن الـ Map مش بيفتكر "شفته" وبس، بيفتكر "شفته فين". - ليه one pass كفاية؟ لو الإجابة
[j, i]وj < i، فـnums[j]اتسجّل قبل ما نوصل لـi. كل زوج بيتلقط عند عنصره التاني. - Edge cases:
[3, 3]، وعنصر شريكه هو نفسه زي[3, 2, 4]مع 6، وسالب وصفر، و index 0.
- value → index.
Setمش هينفع لأن المطلوب الـ index، والـ object هيحوّل الأرقام لـ strings من غير ما تحس. i < nums.lengthمش<=: آخر index هوlength - 1، وnums[length]هتبقىundefinedوالـ need هيبقىNaN.- الشريك المطلوب بالظبط. ده اللي بيحوّل "دوّر على أي حد يكمّلني" لـ lookup واحد في O(1).
hasمشget: لو الشريك في index 0،getهترجّع0وده falsy، فهتفوّت الإجابة. والـ index القديم الأول لأنه الأصغر.- بعد السؤال. لو بدّلت السطرين،
[3, 2, 4]مع 6 هترجّع[0, 0]. - مش هيتنفّذ لأن الإجابة مضمونة، بس الدالة لازم ترجّع حاجة في كل 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²).
هنا الـ Map كان شايل index. طب لو المهم مش "فين" لكن "كام مرة"؟
مثال محلول 2: Valid Anagram
string s و string t فيهم حروف إنجليزي صغيرة بس. هل t هي حروف s بعد ما تتلخبط؟ يعني نفس الحروف، وكل حرف بنفس العدد.
نفكّر فيها مع بعض
- افهم المطلوب: الترتيب مش مهم، المهم عدد كل حرف.
"aab"و"abb"نفس الحروف بأعداد مختلفة: false. - أول حل: sort الاتنين وقارن. سطر واحد، بس
O(n log n). - الجديد هنا إن الـ map بيعدّ بدل ما يفتكر مكان: عدّ حروف
sوحروفtوقارن، فيO(n). - Map ولا array 26؟ الحروف a لـ z بس، فـ array 26 أسرع (مفيش hash خالص)، والـ memory ثابتة
O(1)مهما الـ string طوّل. - array واحدة كفاية:
++لحروفsو--لحروفt. لو أي عداد نزل تحت الصفر،tفيها زيادة، فنعمل early return. - Edge cases: أطوال مختلفة، أعداد مختلفة، strings فاضية.
- ده جزء من صحة الحل، مش optimization. من غيره
s = "ab"وt = "a"هترجّعtrue: الـ check التحت بيلقط الزيادة فيtبس، والطول هو اللي بيلقط النقص. - من غير
fill(0)هتبقىundefined++يعنيNaN. وfill(0)آمنة لأن الصفر primitive، مش array. charCodeAt(i) - 97بيحوّل'a'..'z'لـ0..25على طول. و<لأن آخر index هوlength - 1.- نفس الحساب بالسالب. لو العداد نزل تحت الصفر،
tاستخدمت الحرف ده أكتر منs: early return. - مش محتاجين نلف نتأكد إن كله صفر: مجموع العدادات = الطولين ناقص بعض = صفر، ومفيش سالب، يبقى كلهم صفر.
الـ 26 خانة بتتملا من "listen" وتفضى بـ "silent". صف الحروف هو اسم الخانة، واللي تحته العداد:
ولو الحروف ممكن تبقى أي حاجة، نفس الفكرة بـ Map:
هنا !count.get(ch) مقصودة: undefined (مش موجود) و 0 (خلص) الاتنين معناهم زيادة في t. يعني هنا الـ falsy بتاعة الصفر في صالحنا، عكس Two Sum.
| الطريقة | الوقت | الـ memory | امتى |
|---|---|---|---|
| sort وقارن | O(n log n) | O(n) | أسرع حاجة تكتبها، كبداية |
| array 26 | O(n) | O(1) | a لـ z بس: الأحسن |
Map | O(n) | O(k)، k = عدد الحروف المختلفة | أي حروف: Unicode، أرقام، رموز |
| Input | المتوقع | ليه الحالة دي مهمة |
|---|---|---|
| "aab", "abb" | false | العداد بتاع b هينزل لـ −1 |
| "ab", "a" | false | من غير فحص الطول هترجّع true |
| "", "" | true | الـ loops مش هتلف أصلًا |
| "abc", "cba" | true | مقلوب الكلمة anagram ليها |
for...of بيمشي على الحروف الحقيقية، لكن s[i] و s.length بيعدّوا وحدات UTF-16، والـ emoji بياخد اتنين منهم.
عرفنا نقول إن كلمتين anagram. طب لو عندك 10,000 كلمة وعايز تجمّع كل الـ anagrams مع بعض؟
مثال محلول 3: Group Anagrams
array كلمات بحروف إنجليزي صغيرة. جمّع كل الكلمات اللي anagrams لبعض في group واحدة. ترتيب الـ groups والكلمات جواها مش مهم.
نفكّر فيها مع بعض
- افهم المطلوب: كل group كلمات نفس الحروف بنفس الأعداد، والكلمة اللي مالهاش أصحاب group لوحدها.
- Brute force: كل كلمة تتقارن بكل group بـ
isAnagram: لحدO(n² · k)، وkطول الكلمة. - الجديد هنا إن الـ count (أو الحروف المترتبة) بقى key: لكل كلمة signature واحد لكل الـ anagrams ومختلف لغيرهم، وبعدين grouping pattern عادي.
- Signature 1، الحروف مترتبة:
"tap"بتبقى"apt". دهO(k log k)للكلمة، والمجموعO(n · k log k). - Signature 2، عدد كل حرف: array 26 تتحوّل string. ده
O(k)للكلمة، والمجموعO(n · k). - Edge cases:
""(الـ key string فاضي، عادي جدًا)، كلمة واحدة، و"ab"مع"abb".
- الـ object غالبًا هيشتغل هنا، بس الـ Map هو العادة الآمنة: مفيش keys موروثة، و
.values()جاهزة تحت. sort()من غير comparator صح هنا: الـ default بيرتّب كـ strings، وإحنا فعلًا بنرتّب حروف.- group فاضية أول مرة. لازم قبل الـ push، وإلا
undefined.pushهيضرب error. - بنضيف الكلمة الأصلية، مش الـ signature.
values()بترجّع iterator، والـ[...]بتحوّله array.
الـ signature التاني: عدد كل حرف
- array جديدة لكل كلمة، وإلا العدادات تتراكم من كلمة للتانية.
- نفس العدّ بتاع Valid Anagram،
O(k). - ليه
'#'؟ من غيرها، a = 1 و b = 11 بيطلع"111..."، و a = 11 و b = 1 بيطلع"111..."برضه. وبنحوّل لـ string أصلًا لأن الـ Map بيقارن الـ arrays بالـ reference. - نفس سطور الـ 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
array أرقام ورقم k. رجّع الـ k أرقام اللي اتكرروا أكتر حاجة، بأي ترتيب. الإجابة مضمونة إنها واحدة، والمسألة بتطلب حل أحسن من O(n log n).
نفكّر فيها مع بعض
- أول خطوة: counting pattern،
O(n). - بعد العدّ: sort بالعدد وخد أول
k:O(n log n). والمسألة عايزة أحسن. - Heap حجمه k:
O(n log k)، هتشوفه في Heap. - الجديد هنا إن العدد نفسه بقى index: الـ frequency رقم صحيح من 1 لـ
n، فـbuckets[f]فيها الأرقام اللي اتكررتfمرة، ونمشي من فوق لتحت. ده bucket sort من غير ولا مقارنة. - ليه O(n)؟ العدّ
O(n)، والـ bucketsn + 1خانة، والتوزيعO(m)(عدد الأرقام المختلفة)، والمشيO(n). كلهO(n). - Edge cases: كل الأرقام زي بعض (العدد =
n)، وk= عدد الأرقام المختلفة، وأرقام سالبة.
- counting pattern زي ما هو.
- ليه
+ 1؟ أكبر عدد ممكنn(زي[2, 2, 2])، فمحتاجين index رقمn، يعني طولn + 1. و() => []عشان كل bucket array لوحده. [x, f]destructuring لكل entry، وxبيروح الخانة اللي رقمها عدده. الـ value بقت مكان.- من
nلتحت عشان الأكتر تكرارًا الأول.f >= 1لأن الخانة 0 دايمًا فاضية، وres.length < kبتوقف بدري. - ناخد اللي ناقصنا بس، والـ
breakبيحمي لو الـ bucket فيه أكتر من المطلوب. - الترتيب مش مهم في المسألة.
التلات مراحل: counting، وبعدين توزيع على الـ buckets، وبعدين المشي من فوق:
| الطريقة | الوقت | الـ memory |
|---|---|---|
| counting + sort بالعدد | O(n log n) | O(n) |
| counting + heap حجمه k | O(n log k) | O(n + k) |
| counting + bucket sort | O(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 واحد |
O(n log k)، وبعدين: "بس العدد عمره ما يعدّي n، فأقدر أستخدمه index وأوصل O(n)". ملاحظة إن القيمة محدودة فتنفع index بتتكرر كتير.
كل اللي فات كان Map. آخر مثال بـ Set بس، وفيه loop جوه loop وبرضه O(n). إزاي؟
مثال محلول 5: Longest Consecutive Sequence
array أرقام مش مترتبة. رجّع طول أطول سلسلة أرقام ورا بعض في العدّ (x، x + 1، x + 2...)، والأرقام ممكن تبقى في أي مكان في الـ array. المطلوب O(n).
نفكّر فيها مع بعض
- افهم المطلوب: مش subarray متصل. الـ 1 و 2 و 3 و 4 مبعترين، المهم إن قيمهم ورا بعض.
- أول حل: sort وعدّ،
O(n log n). والمطلوبO(n). - Set عشان "
x + 1موجود؟" تبقى O(1). بس لو من كل رقم مشيت لفوق،[1..n]هياخد حواليn²/2. - الجديد هنا إن مش كل رقم يبدأ عدّ: ابدأ بس من بداية السلسلة، يعني
xالليx - 1بتاعه مش موجود. والـ complexity بتتحسب على البرنامج كله، مش لفة لفة. - ليه O(n)؟ كل سلسلة بتتعدّ مرة واحدة من بدايتها، وكل رقم في سلسلة واحدة. فالـ while على البرنامج كله بتعدّي على كل رقم مرة بالكتير: حوالي
2nعملية. - Edge cases: array فاضية، تكرار، أرقام سالبة.
- بناء الـ Set
O(n)، وبيشيل الـ duplicates لوحده. 0مش 1، عشان الـ array الفاضية إجابتها 0.- على الـ Set مش
nums. لو الـ 1 متكرر 5000 مرة فيnums، كل نسخة هتبقى "بداية" وتعيد نفس المشي. - قلب الحل: لو
x - 1موجود،xهيتعدّ من بداية سلسلته، فنفوّته. lenبيعدّ الطول، وفي نفس الوقت بيحدد الرقم الجايx + len.- نحدّث الـ 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.
الحلول دي شغالة. بس فيه غلطات صغيرة بتطلّع 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.
تمرين: فكّر قبل ما تفتح
array أرقام ورقم k. فيه مكانين مختلفين i و j فيهم نفس الرقم، والمسافة |i - j| أقل من أو تساوي k؟ حاول في O(n).
تلميح 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 دقيقة، ارجع للقالب هنا، وبعدين حاول تاني من غير ما تبص.
- Contains Duplicateأول animation في الفصل: seen-set في أبسط صورة.
- Two Sumالمثال المحلول 1: complement. اسأل قبل ما تسجّل.
- Valid Anagramالمثال المحلول 2: counting بـ array 26، وبعدين جرّب الـ Map.
- Ransom Noteنفس العدّ، بس الزيادة مسموحة في string واحدة بس. أنهي تعدّها وأنهي تطرحها؟
- First Unique Character in a Stringtwo passes: الأولى تعدّ، والتانية تدوّر على أول حرف عدده 1.
- Isomorphic StringsMap من حرف لحرف، ومن الناحية التانية كمان. ليه واحد مش كفاية؟
- Contains Duplicate IIالتمرين اللي فوق: value → آخر index.
- Happy Numberseen-set على أرقام إنت بتولّدها: لو رقم اتكرر يبقى دخلت في cycle.
- Group Anagramsالمثال المحلول 3: grouping. جرّب الـ signatures الاتنين.
- Top K Frequent Elementsالمثال المحلول 4: counting + bucket sort. خلي بالك من
n + 1. - Longest Consecutive Sequenceالمثال المحلول 5: Set + "ابدأ من البداية بس". اشرح ليه O(n) بصوت عالي.
- Valid Sudoku27 Set (صفوف وأعمدة ومربعات)، أو Set واحد بـ composite keys زي
"5 in row 2".
وقبل ما تمشي، الفصل كله في صفحة واحدة.
الخلاصة
| السؤال | الإجابة |
|---|---|
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 زيادة؟