Arrays و Stringsmemory · traversal · in-place · strings · 2D
في JavaScript للانترفيو مسكت الأدوات. دلوقتي هنبص جوه أكتر data structure هتقابلها: الـ array، والـ string اللي هو في الآخر array of chars بس read-only. لما تفهم هي قاعدة إزاي في الـ memory، هتعرف لوحدك ليه عملية O(1) وعملية تانية O(n).
هتطلع من الفصل ده وإنت عارف
- ليه
arr[i]بـ O(1)، وليه الـ insert في النص O(n). - تكتب أي loop من غير off-by-one:
<ولا<=، وn - 1، وi >= 0. - تعمل swap و reverse لجزء من array in-place، وتعدّ الحروف بـ array من 26 خانة.
- تحل Merge Sorted Array و Rotate Array و Longest Common Prefix و Reverse Words، وتعرف ليه كل سطر مكتوب كده.
ليه تفهم الـ array من جوه؟
جرّب ده في دماغك: array فيها 100,000 رقم. nums[70000] بترجع على طول. لكن لو عملت unshift (إضافة في الأول) جوه loop مية ألف مرة، الكود هياخد TLE. نفس الـ array، فليه الفرق ده؟ الإجابة في شكلها جوه الـ memory.
الـ array بالظبط كده: block واحد متصل في الـ memory، الخانات جنب بعض وكلها نفس الحجم. فلو الجهاز عارف عنوان أول خانة (base) وحجم الخانة، عنوان أي خانة هو base + i × size. عملية حسابية واحدة، يعني O(1) مهما الـ array كبرت. بص الفرق بين إنك تقرا بالـ index وإنك تدوّر بالقيمة:
الـ key insight: الـ index هو العنوان. لو معاك index، خطوة واحدة. لو معاك قيمة بس، هتلف عليها، وده O(n).
قبل ما ندخل في العمليات، إزاي تعرف إن المسألة بتختبرك في أساسيات الـ array نفسها؟
إزاي تعرفه من المسألة
الفصل ده مش pattern واحد، ده الأدوات اللي كل الـ patterns بتتبني عليها. الكلمات دي بتقولك إن المسألة محتاجة أداة منهم:
الحاجات اللي في السطر التاني محتاجة pattern فوق الأساسيات: hash map، و sliding window، و prefix sum، و graphs على grid.
| المسألة بتقول | الأداة | هتشوفها في |
|---|---|---|
| عدّل in-place، وفيه مكان فاضي في الآخر | املا من الآخر | Merge Sorted Array |
| زحلق الـ array k خطوات، O(1) memory | k %= n وبعدين reverse تلات مرات | Rotate Array |
| اعكس جزء من الـ array | reverse(arr, l, r) بـ swap | swap و reverse |
| الحروف lowercase English بس | new Array(26).fill(0) و charCodeAt | عدّ الحروف |
| رجّع string بتتبني حتة حتة | parts.push وبعدين join | Reverse Words |
| matrix فيها صفوف وأعمدة | grid[r][c] بـ loop جوه loop | الـ 2D array |
flowchart TD
A["Array / string problem"] --> B{"Edit in place?"}
B -- yes --> C{"Free slots at the end?"}
C -- yes --> D["Fill from the end"]
C -- no --> E["Swap / reverse ranges"]
B -- no --> F{"Counting letters a-z?"}
F -- yes --> G["Array of 26 + charCodeAt"]
F -- no --> H{"Building a string?"}
H -- yes --> I["parts.push + join"]
H -- no --> J["Plain loop: forward, backward, pairs, step k"]
الأسئلة دي بالترتيب ده بتوصّلك للأداة.
أول عمود في الجدول ده كله عن التكلفة. فنبدأ بالسؤال: الـ insert في النص بيكلّف كام بالظبط؟
Insert و delete في النص: ليه O(n)؟
عايز تحط 5 عند index 2 في [3, 8, 1, 9, 4, 7]. مفيش خانة فاضية في النص، الخانات لازقة في بعض. فلازم كل عنصر من index 2 لحد الآخر يتزحلق خطوة يمين. ده بالظبط اللي splice و unshift بيعملوه من جوه:
- بنكبّر الـ array خانة في الآخر. الـ
pushنفسه O(1) amortized: من وقت للتاني الـ engine بيحجز block أكبر وينقل، بس ده نادر فالمتوسط ثابت. - ليه من الآخر؟ لأن لو بدأت من قدّام، هتكتب فوق رقم لسه ما نقلتوش (جرّب في الـ quiz تحت). وليه
i > indexمش>=؟ عندi === indexهتنسخarr[index - 1]فوق مكانه، ولوindex = 0هتقراarr[-1]اللي هوundefined. - كل لفة بتنقل عنصر واحد one step يمين. عدد اللفات
n - index، والـ worst caseindex = 0يعني n نقلة: O(n). - بعد الـ loop،
arr[index]وarr[index + 1]فيهم نفس القيمة، فالخانة دي متاحة نكتب فيها.
لو كتبنا الـ loop من قدّام: for (let i = index + 1; i < arr.length; i++) arr[i] = arr[i - 1]; على نفس المثال، الـ array هتبقى إيه بعد ما نكتب الـ 5؟
[3, 8, 5, 1, 9, 4, 7]عادي[3, 8, 5, 1, 1, 1, 1][3, 8, 5, 9, 4, 7, 7]- error
أول لفة بتنسخ الـ 1 لـ index 3 فالـ 9 بتضيع، والتانية بتنسخ الـ 1 تاني لـ index 4، وهكذا. الـ 1 بيتسحب لحد الآخر. عشان كده لما تنقل يمين، ابدأ من الآخر.
الـ delete هو العكس: كل اللي بعد الـ index يتسحب خطوة شمال. هنا اللف من قدّام هو الصح، لأنك بتقرا arr[i + 1] اللي لسه ما اتكتبش عليه:
القاعدة: اللف بيمشي عكس اتجاه النقل. بتنقل يمين؟ لف من اليمين. بتنقل شمال؟ لف من الشمال. كده دايمًا بتقرا قبل ما تكتب فوق.
| العملية في JS | Complexity | ليه |
|---|---|---|
| arr[i], arr[i] = x, arr.length | O(1) | معادلة العنوان |
| arr.push(x), arr.pop() | O(1) amortized | آخر الـ array، مفيش حد يتزحلق |
| arr.unshift(x), arr.shift() | O(n) | كل العناصر بتتزحلق |
| arr.splice(i, 0, x) | O(n) | اللي بعد i بيتزحلق |
| arr.indexOf(x), arr.includes(x) | O(n) | بحث بالقيمة، لفة كاملة في الـ worst case |
| arr.slice(a, b), [...arr] | O(b - a) / O(n) | بتعمل نسخة جديدة |
| arr.reverse() | O(n) | in-place، بتعكس الـ array كلها |
| arr.sort((a, b) => a - b) | O(n log n) | في Sorting |
عرفنا كل عملية بتكلّف كام. طب إزاي تلف على الـ array نفسها من غير ما تقع في الـ off-by-one؟
أشكال اللف الأربعة
تقريبًا كل loop على array هتكتبها هي واحدة من الأربعة دول. اعرف كل واحدة بتبدأ فين وبتقف فين، والـ off-by-one هيختفي:
- خزّن الطول في
n. الكود بيبقى أقصر، وكل الحدود بتتكتب بـnفتشوف الـ off-by-one بعينك. i < nلأن آخر index هوn - 1. لو كتبتi <= nهتلف لفة زيادة وتقراnums[n]، اللي هوundefinedمن غير أي error.- بيبدأ من
n - 1مشn، وبيقف علىi >= 0مشi > 0. لو كتبت> 0هتنسى index 0، وده bug مش هيبان غير لو الإجابة في أول خانة. - بيبدأ من 1 عشان
nums[i - 1]تبقى موجودة. عدد الأزواج المتجاورةn - 1مش n. i += kبيقفز k كل مرة. آخر حتة ممكن تبقى أقصر من k، وsliceمش بتضرب error لوi + kعدّى الطول، بترجّع اللي موجود بس.
| الـ loop | بتلف كام مرة | قيم i |
|---|---|---|
| for (i = 0; i < n; i++) | n | 0 .. n-1 |
| for (i = 0; i <= n; i++) | n + 1 | 0 .. n (nums[n] = undefined) |
| for (i = 1; i <= n; i++) | n | 1 .. n (عدّ، مش indices) |
| for (i = n - 1; i >= 0; i--) | n | n-1 .. 0 |
| for (i = a; i < b; i++) | b - a | a .. b-1 |
| for (i = a; i <= b; i++) | b - a + 1 | a .. b |
i = 0 و i < n. بتعدّ أرقام من 1 لـ n؟ يبقى i = 1 و i <= n. ده بالظبط الفرق اللي وقّعك في FizzBuzz: كانت عدّ من 1 لـ n، فالـ < نسيت آخر رقم.
ليه تلف من الآخر؟ مثال
عايز لكل عنصر أكبر رقم على يمينه (ولآخر عنصر -1). من الأول، كل عنصر محتاج loop على اللي بعده: O(n²). لكن من الآخر، المعلومة بتتجمّع وإنت ماشي: كل خطوة بتضيف عنصر واحد للي "على اليمين".
new Array(n)بيحجز n خانة من الأول، فنقدر نكتبres[i]بأي ترتيب. لو استخدمتpushوإنت لافف من الآخر، الإجابة هتطلع مقلوبة.-1لأن المسألة بتقول آخر عنصر ياخد -1، والأرقام موجبة. لو الأرقام ممكن تبقى سالبة، ابدأ بـ-Infinity.- الـ backward loop بالظبط: من
n - 1لحد0وشاملة الـ 0. - الترتيب هنا هو الحل كله. بنكتب الإجابة الأول، وبعدين نضم
nums[i]للـ max. لو عكست السطرين،res[i]هتشملnums[i]نفسه، والمطلوب اللي على يمينه بس.
لفة واحدة، يعني O(n) وقت. ده اللي LeetCode 1299 عايزه بالظبط، وهتلاقيه في الـ practice. لاحظ الـ idea نفسها: الاتجاه الصح للّف بيوفّر loop كاملة.
اللف لوحده مش كفاية. كتير من المسائل عايزاك تعدّل الـ array نفسها in-place. أبسط تعديل؟ swap و reverse.
Swap و reverse in-place
arr.reverse() بتعكس الـ array كلها، ومفيهاش parameters لجزء. ومسائل كتير (زي Rotate Array تحت) محتاجة تعكس من l لـ r بس. فلازم تعرف تكتبها بإيدك:
lوrالاتنين inclusive. عشان تعكس الـ array كلها:reverseRange(arr, 0, arr.length - 1)، مشarr.length.l < rمش<=: لما يتقابلوا على نفس العنصر، ده العنصر اللي في النص، ومكانه صح أصلًا في العكس. ولما يعدّوا بعض يبقى خلاص كل زوج اتبدّل.- الـ swap محتاج
tmp: أول ما تكتبarr[l] = arr[r]القيمة القديمة بتضيع. وفيه شكل أقصر:[arr[l], arr[r]] = [arr[r], arr[l]];بس خلي بالك من الـ semicolon اللي قبله (هتشوف ليه في الغلطات). - الاتنين بيقرّبوا خطوة. عدد الـ swaps حوالي
(r - l + 1) / 2، يعني O(n) وقت و O(1) memory.
ده نفس قالب الـ opposite ends اللي هتشوفه بالتفصيل في Two Pointers. هنا هو أداة صغيرة هنستخدمها في Rotate Array و Reverse Words.
الـ array بتتعدّل بسهولة كده. طب الـ string؟ جرّب s[0] = 'X' وشوف هيحصل إيه.
الـ strings في JS: immutable
الـ string بيتقري زي الـ array بالظبط: s[i] و s.length الاتنين O(1). الفرق إنه immutable: مش هتقدر تغيّر حرف جواه. أي "تعديل" بيعمل string جديد. فالطريقة: حوّله array، عدّل، وارجع join:
- السطر ده مش بيعمل حاجة. في الـ sloppy mode بيتجاهله ساكت، وفي الـ strict mode (classes و modules) بيضرب
TypeError: Cannot assign to read only property. في الحالتينsفاضلة'cairo'. split('')بيدّيك array of chars حقيقية تعدّل فيها براحتك.[...s]نفس الكلام للحروف الإنجليزي.join('')بـ string فاضي. لو كتبتjoin()من غير argument هيحط commas:'C,a,i,r,o'.- هنا
<=صح، لأننا بنعدّ من 1 لـ 5 مش بنلف على indices. نفس قاعدة الـ FizzBuzz. - بنلم الحتت في array ونعمل
joinمرة واحدة في الآخر. في Java و Python، الـ+=على string جوه loop ممكن يبقى O(n²) لأن كل مرة بيتعمل نسخة. V8 بيعمل optimization (ropes) فالـ+=في JS غالبًا تمام، بس الـ parts + join أوضح، وبيسهّل الـ separators، وبيشتغل صح في أي لغة. slice(start, end)مش بياخد الـ end. الطول =end - start، زيfor (i = start; i < end)بالظبط. هتحتاج الحتة دي في Longest Common Prefix.
| العملية | Complexity | ملاحظة |
|---|---|---|
| s.length, s[i], s.at(-1) | O(1) | s.at(-1) آخر حرف |
| s.slice(a, b) | O(b - a) | string جديد، الـ b مش داخل |
| s.indexOf(t), s.includes(t) | لحد O(n · m) | مش O(1)، فخلي بالك منها جوه loop |
| s.split(sep), arr.join(sep) | O(n) | split(' ') بتطلّع strings فاضية لو فيه مسافتين ورا بعض |
| s.trim(), s.toLowerCase() | O(n) | بيرجّعوا string جديد |
| a === b, a < b | O(n) | المقارنة حرف حرف: '10' < '9' بتطلع true |
أشهر حاجة بتتعمل على string: إنك تعدّ الحروف. وفيه طريقة أسرع من أي Map لما الحروف تبقى a لـ z بس.
عدّ الحروف بـ array من 26
لما المسألة تقول "lowercase English letters"، يبقى عندك 26 احتمال بس. فبدل Map، اعمل array من 26 خانة: خانة لكل حرف. والسؤال الوحيد: إزاي تحوّل الحرف لـ index؟ هنا ييجي charCodeAt:
new Array(26)لوحدها 26 خانة فاضية (holes)، وcount[i]++على خانة فاضية بيدّيNaN. الـ.fill(0)هو اللي بيحط أصفار حقيقية.for...ofبيدّيك الحروف نفسها، ومش محتاج index هنا.charCodeAt(0)بيرجّع رقم الحرف:'a'= 97 لحد'z'= 122. لو طرحت 97 تاخد 0 لـ 25، يعني index جاهز. في C++ بتكتبc - 'a'، لكن في JS'c' - 'a'بتطلعNaN. (الكبيرة بتبدأ من 65، والأرقام من 48.)- كل حرف بيزوّد خانته. O(1) لكل حرف، فالكل O(n).
- الرجوع من index لحرف:
String.fromCharCode(97 + i). ولاحظ إن اللف على الـ 26 خانة بيطلّع الحروف مترتبة أبجديًا ببلاش.
charCodeAt(0) - 97، ومفيش collisions خالص. أسرع من الـ Map، والـ memory ثابتة 26 مهما الـ string طوّل، يعني O(1). لكن لو الـ keys ممكن تبقى أي حاجة (أي حرف Unicode، أرقام، كلمات)، هتحتاج Map، وده الفصل الجاي.
لحد دلوقتي كل حاجة كانت صف واحد. طب لو الداتا جدول، صفوف وأعمدة؟
الـ 2D array: صفوف وأعمدة
الـ matrix في JS هي array جواها arrays: كل array جوه هي صف. فـ grid[r] هو الصف كله، و grid[r][c] هي الخانة. الصف الأول، بعدين العمود، دايمًا.
- عدد الصفوف = عدد الـ arrays اللي جوه. عدد الأعمدة = طول صف واحد. ده بيفترض إن فيه صف واحد على الأقل، فلو الـ grid ممكن تبقى فاضية، اعمل check الأول.
-Infinityمش 0: لو كل المجاميع سالبة، الـ 0 هيطلع إجابة مش موجودة أصلًا.- الـ
rowSumبيتعرّف جوه الـ loop البراني، فبيرجع 0 مع كل صف. لو عرّفته برا، المجاميع هتتراكم من صف للتاني. grid[r][c]، مشgrid[c][r]. لو الـ matrix مش مربعة وعكستهم، هتقرا برا الحدود وتاخدundefined.- الـ update بعد ما الصف يخلص. لو حطيته جوه الـ loop الجوانية هتقارن مجاميع ناقصة، ومع أرقام سالبة الإجابة هتطلع غلط.
الوقت O(rows × cols): كل خانة بتتزار مرة. وتلات حاجات هتحتاجهم كتير:
لو لفّيت عمود عمود، الـ loop البرانية بقت على c، بس الوصول لسه grid[r][c]. وشرط الحدود ده هتكتبه في كل مسألة grid لما تبص على الجيران. الـ matrix كـ graph (جزر، flood fill، BFS) ليها فصل لوحدها: Graphs على Grid.
كده الأدوات كلها معاك. يلا نستخدمها، وأول مسألة بتجمع الـ shifting مع اللف من الآخر.
مثال محلول 1: Merge Sorted Array
عندك nums1 فيها m رقم حقيقي مترتبين، وبعدهم n صفر مجرد أماكن فاضية. و nums2 فيها n رقم مترتبين. ادمج الاتنين جوه nums1 نفسها، والنتيجة كلها تبقى مترتبة. مفيش return.
نفكّر فيها مع بعض
- افهم المطلوب: الإجابة لازم تتكتب جوه
nums1، والأصفار اللي في آخرها هي المكان المتاح. - Brute force: حط
nums2في الأصفار واعمل sort:O((m+n) log(m+n)). شغال، بس رامي معلومة إن الاتنين مترتبين. - Merge عادي من الأول في array جديدة:
O(m+n)، بس محتاجO(m+n)memory. ولو عملته من الأول جوهnums1نفسها، هتكتب فوق أرقام لسه ما قريتهاش. شوف بنفسك:
- الـ key insight: الأماكن الفاضية في الآخر. فلو ملينا من الآخر بالأكبر، عمرنا ما هنكتب فوق حاجة لسه محتاجينها. نفس قاعدة الـ insert: اللف عكس اتجاه النقل.
- الخطة:
iعلى آخر رقم حقيقي فيnums1، وjعلى آخرnums2، وkعلى آخر خانة. كل لفة: الأكبر من الاتنين يروحk. - Edge cases:
n = 0،m = 0، كلnums2أصغر منnums1، وأرقام متساوية.
m - 1مشnums1.length - 1: آخر رقم حقيقي. اللي بعده أصفار ملهاش معنى.- أكبر رقم في الاتنين مكانه آخر خانة أكيد، فبنبدأ نكتب من هنا.
- ليه
j >= 0بس؟ لوnums2خلصت، اللي فاضل فيnums1في مكانه الصح أصلًا، فنقف. لوnums1خلصت الأول، الشرط ده بيخلّينا نكمّل ننقلnums2. i >= 0الأول عشان الـ short-circuit: لوi = -1مش هنقراnums1[-1]خالص. و>ولا>=مش فارقة هنا: في التساوي أي واحد فيهم صح.- رقم
nums1أكبر، فبيتنقل لـk، ومكانه القديم بقى فاضي ينفع نكتب فيه بعدين. - رقم
nums2أكبر أو مساوي، فبينزل فيk. - كل لفة بتملا خانة واحدة بالظبط، فـ
k--في الحالتين. الـ invariant:k - i = j + 1، يعني طول ماj >= 0الـkقدّامiومش هيكتب فوق رقم لسه ما اتقراش.
| Input | المتوقع | ليه الحالة دي مهمة |
|---|---|---|
| [1], 1, [], 0 | [1] | j = -1 من الأول، والـ loop مش بتدخل |
| [0], 0, [5], 1 | [5] | i = -1 من الأول، فالـ i >= 0 بتحمينا |
| [4,5,6,0,0,0], 3, [1,2,3], 3 | [1,2,3,4,5,6] | كل nums1 بتتنقل، وبعدها nums2 كلها |
| [1,2,3,0,0,0], 3, [4,5,6], 3 | [1,2,3,4,5,6] | nums1 ما بتتحركش خالص |
| [2,2,0,0], 2, [2,2], 2 | [2,2,2,2] | التساوي |
التعقيد: كل لفة بتملا خانة، والخانات m + n بالكتير، يعني O(m + n) وقت و O(1) memory.
k دايمًا قدّام i بـ j + 1 خانة، فعمري ما هكتب فوق رقم لسه محتاجه". الجملة دي هي الفرق بين إنك حافظ الحل وإنك فاهمه.
هنا الـ in-place كان سهل لأن فيه مكان فاضي. طب لو مفيش ولا خانة فاضية، وعايز تزحلق الـ array كلها؟
مثال محلول 2: Rotate Array
زحلق الـ array لليمين k خطوات in-place: كل عنصر يمشي k خانة يمين، واللي يطلع من الآخر يلف ويدخل من الأول. يعني آخر k عناصر بييجوا قدّام.
الجديد هنا إن مفيش ولا خانة فاضية زي Merge. الحل هيتبني كله على reverseRange اللي كتبناها فوق.
نفكّر فيها مع بعض
- Brute force: زحلق خطوة واحدة (O(n))، وكرّر k مرة:
O(n · k). مع n و k لحد 10⁵ ده 10¹⁰، TLE. - بـ array إضافية: العنصر اللي عند
iمكانه الجديد(i + k) % n. O(n) وقت بس O(n) memory. قوله كبداية في الانترفيو. - أول حاجة:
k %= n. اللف n مرة بيرجّع الـ array زي ما هي، فـ k = 10 على 7 عناصر هي هي k = 3. - الـ key insight: قسّم الـ array لجزئين:
Aأولn - k، وBآخرk. إحنا عايزينA BتبقىB A. وده بيتعمل بتلات reverses. - Edge cases:
k = 0،kأكبر من n أو مضاعف ليه، وn = 1.
ليه الخطوة 1 بتدّي rev(B) | rev(A)؟ لأن عكس الـ array كلها بيخلّي آخر عنصر أول عنصر. فالـ block اللي كان في الآخر (B) بيبقى في الأول، بس كل block جوه نفسه مقلوب. الخطوتين 2 و 3 بيصلّحوا القلبة دي، كل block لوحده، من غير ما يغيّروا مكانه.
- من غير الـ
%:k = 10على 7 عناصر هتخلّي الخطوة 2 تعكس من 0 لـ 9، فتقراundefinedمن برا وتكبّر الـ array لـ 10 خانات. جرّبتها: النتيجة[undefined × 3, 1, 2, ...]. - الخطوة 1:
A Bبقتrev(B) rev(A). - أول k خانات هما
rev(B)، والـk - 1عشان الـ r inclusive. لوk = 0بتبقىreverse(0, -1)والـl < rبتمنع أي حاجة. تمام. - من
kلـn - 1هوrev(A)، وبعد العكس يرجعA. - نفس
reverseRangeبالـ destructuring swap. السطر اللي قبل الـ swap (while) مش بيتأثر بموضوع الـ semicolon، لأن سطر الـ swap أول statement في الـ block.
| Input | المتوقع | ليه الحالة دي مهمة |
|---|---|---|
| [1..7], k = 0 | [1..7] | الخطوة 1 و 3 بيلغوا بعض، والخطوة 2 مش بتعمل حاجة |
| [1..7], k = 7 | [1..7] | 7 % 7 = 0 |
| [1..7], k = 10 | [5,6,7,1,2,3,4] | من غير % الـ array بتبوظ |
| [1], k = 5 | [1] | 5 % 1 = 0 |
| [-1,-100,3,99], k = 2 | [3,99,-1,-100] | أرقام سالبة، والـ A و B نفس الطول |
التعقيد: كل عنصر بيتبدّل مرتين بالكتير (مرة في العكس الكبير ومرة في جزءه)، يعني O(n) وقت و O(1) memory.
لحد دلوقتي كنا شغالين على array واحدة. طب لو عندك كذا string وعايز تقارنهم ببعض؟
مثال محلول 3: Longest Common Prefix
عندك array of strings. رجّع أطول بداية مشتركة بينهم كلهم. لو مفيش ولا حرف مشترك في الأول، رجّع "".
الجديد هنا إن بنلف على كذا string في نفس الوقت بنفس الـ index (عمود عمود)، وبنقطع النتيجة بـ slice.
نفكّر فيها مع بعض
- افهم المطلوب: الـ prefix المشترك لازم يكون بداية لكل كلمة، فهو مش ممكن يبقى أطول من أقصر كلمة.
- Horizontal: خد أول كلمة كـ prefix، وقصّرها مع كل كلمة لحد ما تبقى بداية ليها. شغال، بس بيعمل strings جديدة كتير.
- Vertical (الأوضح): بص على العمود
i: الحرف رقم i في كل الكلمات. لو كلهم زي بعض، كمّل. أول ما عمود يختلف أو كلمة تخلص، الإجابة هي الحروف اللي قبل i. - Edge cases: كلمة واحدة بس، كلمة فاضية، كل الكلمات زي بعض.
- أي حرف في الـ prefix لازم يكون في أول كلمة، فهي المرجع. أي كلمة تانية كانت تنفع برضه.
iهو رقم العمود، وبيقف عند طولfirstلأن الـ prefix مش هيعدّيها.sبيبدأ من 1، لأن 0 هيfirstنفسها.- سببين للوقوف: الكلمة خلصت (
i === strs[s].length)، أو الحرف مختلف. في JS،strs[s][i]بعد الآخر بترجعundefinedفالشرط التاني هيمسكها لوحده، بس اكتبها صريحة: أوضح، وفي لغات تانية القراية برا الحدود bug. - early return بـ
slice(0, i): الحروف من 0 لـi - 1، وهي بالظبط الأعمدة اللي اتطابقت. الـ i نفسه هو أول عمود بايظ، فمش داخل. - لو الـ loop خلصت من غير return، يبقى
firstكلها بداية لكل الكلمات.
| Input | المتوقع | ليه الحالة دي مهمة |
|---|---|---|
| ["solo"] | "solo" | الـ loop الجوانية مش بتدخل، فبنوصل لـ return first |
| [""] | "" | first.length = 0، فالـ loop مش بتدخل |
| ["ab", "a"] | "a" | الكلمة التانية خلصت قبل أي اختلاف |
| ["abc", "abd", ""] | "" | كلمة فاضية في الآخر |
| ["same", "same"] | "same" | كلهم زي بعض |
التعقيد: في الـ worst case بنبص على كل الحروف مرة: O(S)، و S هو مجموع الحروف. وبالظبط n × (طول الـ prefix + 1) مقارنة بالكتير. والـ memory O(1) غير الإجابة.
O(n log n) مقارنات.
هنا قرينا الـ strings بس من غير ما نبني حاجة. طب لو عايز تفكّك string لكلمات وتبني واحد جديد، والمسافات بايظة؟
مثال محلول 4: Reverse Words in a String
اعكس ترتيب الكلمات في string (مش الحروف). الكلمة حروف ورا بعض من غير مسافة. ممكن يبقى فيه مسافات في الأول والآخر، أو أكتر من مسافة بين كلمتين. الإجابة كلمات بينهم مسافة واحدة بالظبط، ومن غير مسافات على الأطراف.
الجديد هنا إن بنعمل parsing: نقطّع string لكلمات وسط مسافات زيادة، ونبني output جديد بـ parts + join.
نفكّر فيها مع بعض
- افهم المطلوب: المسافات الزيادة تختفي، والكلمات نفسها ما تتعكسش من جوه.
- في JS فيه one-liner:
trimوبعدينsplitعلى أي عدد مسافات وبعدينreverseوjoin. O(n)، وده كويس تبدأ بيه. - الـ interviewer هيقولك: من غير split. امشي بـ index من الآخر: فوّت المسافات، علّم آخر الكلمة، ارجع لحد المسافة اللي قبلها، واقطع الكلمة بـ slice. الكلمات بتطلع بالترتيب المعكوس لوحدها.
- Edge cases: مسافات في الأول والآخر، مسافات كتير ورا بعض، كلمة واحدة.
- من غير
trim، الـ split هيطلّع''في الأول أو الآخر:' a b '.split(/\s+/)بتدّي['', 'a', 'b', '']. /\s+/معناها مسافة واحدة أو أكتر كـ separator. لو كتبتsplit(' ')، كل مسافتين ورا بعض هيطلّعوا string فاضي:' a b'.split(' ')بتدّي['', '', 'a', 'b'].reverseهنا على الـ array الجديدة اللي طلعت من الـ split، مش علىs.join(' ')بمسافة واحدة. ولاحظ إن كل خطوة O(n)، فالكل O(n).
- بنبدأ من الآخر، فأول كلمة نلاقيها هي آخر كلمة. الترتيب المعكوس بييجي ببلاش من غير
reverse. - نفوّت أي مسافات. الـ
i >= 0الأول عشان ما نقراش برا الـ string. - لو خلصنا وإحنا بنفوّت مسافات، يبقى مفيش كلمات تاني. من غير السطر ده هنعمل push لكلمة فاضية، والنتيجة هتطلع
"do can we "بمسافة زيادة في الآخر (جرّبتها). endهو آخر حرف في الكلمة. بعدينiبيرجع لحد ما يقف على المسافة اللي قبل الكلمة، أو-1لو الكلمة في أول الـ string.i + 1لأنiواقف على المسافة، والكلمة بتبدأ بعدها. وend + 1لأنsliceمش بياخد الـ end. يعني الكلمة منi + 1لـendشاملين.- parts + join زي ما اتعلمنا: مسافة واحدة بين كل كلمتين ومفيش أطراف.
| Input | المتوقع | ليه الحالة دي مهمة |
|---|---|---|
| "one" | "one" | كلمة واحدة ومفيش مسافات خالص |
| " a " | "a" | مسافات على الطرفين، والـ break لازم يشتغل |
| "x y" | "y x" | أكتر من مسافة في النص |
| "a b" | "b a" | الكلمة الأولى بتخلص عند i = -1، فالـ slice(0, ...) |
التعقيد: i بيعدّي على كل حرف مرة واحدة، و slice بينسخ كل حرف في كلمة مرة: O(n) وقت، و O(n) memory للإجابة، ودي لازمة لأن الـ strings في JS immutable.
دي الأدوات والأمثلة. قبل ما تتمرن، خد الغلطات اللي بتوقّع الناس في الحاجات دي بالذات.
غلطات مشهورة
1. <= وإنت بتلف على indices
3 + undefined بيدّي NaN، ومن غير أي error. على indices دايمًا i < n. الـ <= للعدّ من 1 لـ n بس.
2. تعدّل string بالـ index
اعمل string جديد: s = 'H' + s.slice(1)، أو split('') وعدّل وارجع join('').
3. new Array(26) من غير fill(0)
undefined + 1 بيدّي NaN، وبعدها كل مقارنة هتطلع false. الصح new Array(26).fill(0).
4. Matrix بـ fill لـ array
fill بيحط نفس الـ reference في التلات خانات، فالتلات صفوف هما array واحدة. الصح Array.from({ length: 3 }, () => new Array(2).fill(0))، لأن الـ function بتتنادى لكل صف فبتعمل array جديدة.
5. Destructuring swap من غير semicolon قبله
لو السطر بيبدأ بـ [ والسطر اللي قبله مالوش ;، الـ JS بتلزقهم. النتيجة: الـ swap ما حصلش، و n بقت array. حط semicolons، أو استخدم tmp.
6. unshift أو shift جوه loop
في تجربة على Node، 100,000 unshift خدوا حوالي 1.4 ثانية، و push وبعدين reverse مرة واحدة خدوا 3 ms. ابني من الآخر، أو اكتب بالـ index في array محجوزة بـ new Array(n).
فاكر كل ده؟ اختبر نفسك.
اختبر نفسك
loop بتلف على n عنصر، وجوّاها res.unshift(x). الـ complexity كام؟
- O(n)
- O(n log n)
- O(n²)
- O(1)
كل unshift بيزحلق كل اللي في res خطوة: 0 + 1 + 2 + ... + (n - 1) ≈ n²/2 نقلة.
nums = [1, 2, 3, 4, 5] و k = 7. بعد Rotate Array هتبقى إيه؟
[3, 4, 5, 1, 2][4, 5, 1, 2, 3][1, 2, 3, 4, 5]- error لأن k أكبر من n
7 % 5 = 2، فآخر عنصرين (4 و 5) ييجوا قدّام.
في Merge Sorted Array، ليه بنملا من الآخر؟
- عشان أسرع من الأول
- عشان الأماكن الفاضية في الآخر، فالكتابة عند
kعمرها ما بتمسح رقم لسه ما اتقراش - عشان الـ arrays مترتبة تصاعدي
- مش فارقة، من الأول صح برضه
الاتنين O(m + n). الفرق في الصحة: من الأول بتكتب فوق أرقام nums1 قبل ما تقراها، زي ما شفت في الـ animation الغلط.
'interview'.slice(2, 5) بترجّع إيه؟
'terv''nte''ter''inter'
من index 2 لحد 4 (الـ 5 مش داخل): t و e و r. الطول 5 - 2 = 3.
في greatestToRight، لو بدّلنا السطرين: maxSoFar = Math.max(...) الأول وبعده res[i] = maxSoFar، إيه اللي هيحصل؟
- نفس النتيجة
res[i]هيشملnums[i]نفسه، فالإجابة هتبقى غلط- infinite loop
- الإجابة هتطلع مقلوبة
المطلوب أكبر رقم على اليمين بس. لو ضمّيت nums[i] الأول، أول عنصر في [4, 9, 2] مثلًا هياخد 9 صح بالصدفة، لكن الـ 9 نفسها هتاخد 9 بدل 2.
تمرين: فكّر قبل ما تفتح
string فيه حروف lowercase بس. رجّع index أول حرف ما اتكررش خالص، ولو مفيش رجّع -1.
تلميح 1
إنت مش هتعرف إن حرف "ما اتكررش" غير لما تشوف الـ string كله. فمحتاج لفتين: واحدة تعدّ، وواحدة تدوّر.
تلميح 2
العدّ بـ array من 26. واللفة التانية على الـ string بالترتيب، مش على الـ 26 خانة، عشان المطلوب أول واحد في الـ string مش أول واحد أبجديًا.
الحل
لفتين O(n)، والـ memory 26 خانة ثابتة: O(1). لاحظ s.charCodeAt(i): بتاخد index الحرف جوه الـ string مباشرة من غير ما تعمل s[i] الأول.
جاهز؟ دلوقتي التمرين الحقيقي على LeetCode.
اتمرن على LeetCode بالترتيب
كل مسألة بتضيف فكرة واحدة. لو قعدت أكتر من 25 دقيقة على واحدة، ارجع للجزء بتاعها هنا، وبعدين حاول تاني من غير ما تبص.
- Concatenation of Arrayتسخين على الـ indices:
ans[i + n]. - Running Sum of 1d Arrayforward loop بيستخدم العنصر اللي قبله. أول لمحة من Prefix Sum.
- Replace Elements with Greatest Element on Right Sideالـ backward loop اللي شفناه، وترتيب السطرين.
- Plus Onebackward loop مع carry. جرّب
[9, 9, 9]: الـ array لازم تكبر. - Reverse String
reverseRangeعلى الكل بالظبط. - Merge Sorted Arrayالمثال المحلول 1. اكتبه من دماغك وقول الـ invariant.
- Rotate Arrayالمثال المحلول 2. اكتب الإثبات بتاع A و B على ورقة.
- Longest Common Prefixالمثال المحلول 3: لف على كذا string بنفس الـ index.
- First Unique Character in a Stringالـ 26-array ولفتين. (التمرين اللي فوق.)
- Reverse Words in a String IIIاعكس كل كلمة من جوه: split و reverse لكل حتة، وبعدين join.
- Reverse Words in a Stringالمثال المحلول 4. حلها مرة بالـ one-liner ومرة من غير split.
- Richest Customer Wealthأول matrix: مجموع كل صف.
- Transpose Matrixmatrix مش مربعة: الإجابة
cols × rows، وres[c][r] = grid[r][c]. - Spiral Matrixاختياري: أربع حدود بتقرّب من بعض. لو عدّت من غير off-by-one، يبقى الـ loops بقت في إيدك.
خلصتهم؟ خد الفصل كله في صفحة واحدة.
الخلاصة
| السؤال | الإجابة |
|---|---|
< ولا <=؟ | indices: i < n. عدّ من 1 لـ n: i <= n. reverse أو زوج: l < r. |
| insert أو delete في النص؟ | O(n). لو جوه loop بقت O(n²): ابني array جديدة أو املا من الآخر. |
| in-place وفيه مكان فاضي في الآخر؟ | املا من الآخر (Merge Sorted Array). |
| in-place ومفيش مكان خالص؟ | swap و reverse لأجزاء (Rotate Array). |
| بتعدّ حروف a لـ z؟ | array من 26 و charCodeAt(0) - 97. أي keys تانية: Map. |
| بتبني string؟ | parts.push وبعدين join. وخلي بالك إن slice مش بياخد الـ end. |
| matrix؟ | grid[r][c]، rows = grid.length، cols = grid[0].length. |
الفصل الجاي: الـ array من 26 كانت hash map صغير: الحرف بيتحوّل لـ index في O(1). طب لو الـ key رقم أي حاجة، أو كلمة كاملة؟ هنا ييجي Hash Map و Set: بيدّوا أي key "عنوان" في O(1) في المتوسط، وده اللي بيحوّل حلول كتير من O(n²) لـ O(n).