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.

تشبيه صف كراسي في سينما، مترقّمة ورا بعض. لو تذكرتك كرسي 14، بتروح له على طول، مش بتعدّ الكراسي من الأول. لكن لو واحد عايز يقعد في النص والصف مليان، كل اللي على يمينه لازم يقوم ويتزحزح كرسي.

الـ array بالظبط كده: block واحد متصل في الـ memory، الخانات جنب بعض وكلها نفس الحجم. فلو الجهاز عارف عنوان أول خانة (base) وحجم الخانة، عنوان أي خانة هو base + i × size. عملية حسابية واحدة، يعني O(1) مهما الـ array كبرت. بص الفرق بين إنك تقرا بالـ index وإنك تدوّر بالقيمة:

الـ key insight: الـ index هو العنوان. لو معاك index، خطوة واحدة. لو معاك قيمة بس، هتلف عليها، وده O(n).

طب و JS؟ الـ arrays في JS من جوه objects، بس V8 بيخزّن الـ array العادية (عناصر ورا بعض من غير holes) في block متصل. فالـ model ده هو اللي بيحكم الـ performance بتاعك فعلًا.

قبل ما ندخل في العمليات، إزاي تعرف إن المسألة بتختبرك في أساسيات الـ array نفسها؟

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

الفصل ده مش pattern واحد، ده الأدوات اللي كل الـ patterns بتتبني عليها. الكلمات دي بتقولك إن المسألة محتاجة أداة منهم:

لما تشوف: in-placeO(1) extra spacemerge two sorted arraysrotate / shift by k reverselowercase English letterscount charactersm x n matrix return a stringcommon prefix
ومش هي لوحدها لو: pair with sum, unsortedlongest substring with a conditionmany range-sum queriesislands / connected cells

الحاجات اللي في السطر التاني محتاجة pattern فوق الأساسيات: hash map، و sliding window، و prefix sum، و graphs على grid.

المسألة بتقولالأداةهتشوفها في
عدّل in-place، وفيه مكان فاضي في الآخراملا من الآخرMerge Sorted Array
زحلق الـ array k خطوات، O(1) memoryk %= n وبعدين reverse تلات مراتRotate Array
اعكس جزء من الـ arrayreverse(arr, l, r) بـ swapswap و reverse
الحروف lowercase English بسnew Array(26).fill(0) و charCodeAtعدّ الحروف
رجّع string بتتبني حتة حتةparts.push وبعدين joinReverse 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 بيعملوه من جوه:

  1. بنكبّر الـ array خانة في الآخر. الـ push نفسه O(1) amortized: من وقت للتاني الـ engine بيحجز block أكبر وينقل، بس ده نادر فالمتوسط ثابت.
  2. ليه من الآخر؟ لأن لو بدأت من قدّام، هتكتب فوق رقم لسه ما نقلتوش (جرّب في الـ quiz تحت). وليه i > index مش >=؟ عند i === index هتنسخ arr[index - 1] فوق مكانه، ولو index = 0 هتقرا arr[-1] اللي هو undefined.
  3. كل لفة بتنقل عنصر واحد one step يمين. عدد اللفات n - index، والـ worst case index = 0 يعني n نقلة: O(n).
  4. بعد الـ 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] اللي لسه ما اتكتبش عليه:

القاعدة: اللف بيمشي عكس اتجاه النقل. بتنقل يمين؟ لف من اليمين. بتنقل شمال؟ لف من الشمال. كده دايمًا بتقرا قبل ما تكتب فوق.

العملية في JSComplexityليه
arr[i], arr[i] = x, arr.lengthO(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 أو نصها، بتزحلق اللي بعدها: O(n). ولو حطيتها جوه loop بقت O(n²). الآخر بس هو الرخيص.

عرفنا كل عملية بتكلّف كام. طب إزاي تلف على الـ array نفسها من غير ما تقع في الـ off-by-one؟

أشكال اللف الأربعة

تقريبًا كل loop على array هتكتبها هي واحدة من الأربعة دول. اعرف كل واحدة بتبدأ فين وبتقف فين، والـ off-by-one هيختفي:

  1. خزّن الطول في n. الكود بيبقى أقصر، وكل الحدود بتتكتب بـ n فتشوف الـ off-by-one بعينك.
  2. i < n لأن آخر index هو n - 1. لو كتبت i <= n هتلف لفة زيادة وتقرا nums[n]، اللي هو undefined من غير أي error.
  3. بيبدأ من n - 1 مش n، وبيقف على i >= 0 مش i > 0. لو كتبت > 0 هتنسى index 0، وده bug مش هيبان غير لو الإجابة في أول خانة.
  4. بيبدأ من 1 عشان nums[i - 1] تبقى موجودة. عدد الأزواج المتجاورة n - 1 مش n.
  5. i += k بيقفز k كل مرة. آخر حتة ممكن تبقى أقصر من k، و slice مش بتضرب error لو i + k عدّى الطول، بترجّع اللي موجود بس.
الـ loopبتلف كام مرةقيم i
for (i = 0; i < n; i++)n0 .. n-1
for (i = 0; i <= n; i++)n + 10 .. n (nums[n] = undefined)
for (i = 1; i <= n; i++)n1 .. n (عدّ، مش indices)
for (i = n - 1; i >= 0; i--)nn-1 .. 0
for (i = a; i < b; i++)b - aa .. b-1
for (i = a; i <= b; i++)b - a + 1a .. b
قاعدة الـ FizzBuzz بتلف على indices؟ يبقى i = 0 و i < n. بتعدّ أرقام من 1 لـ n؟ يبقى i = 1 و i <= n. ده بالظبط الفرق اللي وقّعك في FizzBuzz: كانت عدّ من 1 لـ n، فالـ < نسيت آخر رقم.

ليه تلف من الآخر؟ مثال

عايز لكل عنصر أكبر رقم على يمينه (ولآخر عنصر -1). من الأول، كل عنصر محتاج loop على اللي بعده: O(n²). لكن من الآخر، المعلومة بتتجمّع وإنت ماشي: كل خطوة بتضيف عنصر واحد للي "على اليمين".

  1. new Array(n) بيحجز n خانة من الأول، فنقدر نكتب res[i] بأي ترتيب. لو استخدمت push وإنت لافف من الآخر، الإجابة هتطلع مقلوبة.
  2. -1 لأن المسألة بتقول آخر عنصر ياخد -1، والأرقام موجبة. لو الأرقام ممكن تبقى سالبة، ابدأ بـ -Infinity.
  3. الـ backward loop بالظبط: من n - 1 لحد 0 وشاملة الـ 0.
  4. الترتيب هنا هو الحل كله. بنكتب الإجابة الأول، وبعدين نضم 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 بس. فلازم تعرف تكتبها بإيدك:

  1. l و r الاتنين inclusive. عشان تعكس الـ array كلها: reverseRange(arr, 0, arr.length - 1)، مش arr.length.
  2. l < r مش <=: لما يتقابلوا على نفس العنصر، ده العنصر اللي في النص، ومكانه صح أصلًا في العكس. ولما يعدّوا بعض يبقى خلاص كل زوج اتبدّل.
  3. الـ swap محتاج tmp: أول ما تكتب arr[l] = arr[r] القيمة القديمة بتضيع. وفيه شكل أقصر: [arr[l], arr[r]] = [arr[r], arr[l]]; بس خلي بالك من الـ semicolon اللي قبله (هتشوف ليه في الغلطات).
  4. الاتنين بيقرّبوا خطوة. عدد الـ 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:

  1. السطر ده مش بيعمل حاجة. في الـ sloppy mode بيتجاهله ساكت، وفي الـ strict mode (classes و modules) بيضرب TypeError: Cannot assign to read only property. في الحالتين s فاضلة 'cairo'.
  2. split('') بيدّيك array of chars حقيقية تعدّل فيها براحتك. [...s] نفس الكلام للحروف الإنجليزي.
  3. join('') بـ string فاضي. لو كتبت join() من غير argument هيحط commas: 'C,a,i,r,o'.
  4. هنا <= صح، لأننا بنعدّ من 1 لـ 5 مش بنلف على indices. نفس قاعدة الـ FizzBuzz.
  5. بنلم الحتت في array ونعمل join مرة واحدة في الآخر. في Java و Python، الـ += على string جوه loop ممكن يبقى O(n²) لأن كل مرة بيتعمل نسخة. V8 بيعمل optimization (ropes) فالـ += في JS غالبًا تمام، بس الـ parts + join أوضح، وبيسهّل الـ separators، وبيشتغل صح في أي لغة.
  6. 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 < bO(n)المقارنة حرف حرف: '10' < '9' بتطلع true

أشهر حاجة بتتعمل على string: إنك تعدّ الحروف. وفيه طريقة أسرع من أي Map لما الحروف تبقى a لـ z بس.

عدّ الحروف بـ array من 26

لما المسألة تقول "lowercase English letters"، يبقى عندك 26 احتمال بس. فبدل Map، اعمل array من 26 خانة: خانة لكل حرف. والسؤال الوحيد: إزاي تحوّل الحرف لـ index؟ هنا ييجي charCodeAt:

  1. new Array(26) لوحدها 26 خانة فاضية (holes)، و count[i]++ على خانة فاضية بيدّي NaN. الـ .fill(0) هو اللي بيحط أصفار حقيقية.
  2. for...of بيدّيك الحروف نفسها، ومش محتاج index هنا.
  3. charCodeAt(0) بيرجّع رقم الحرف: 'a' = 97 لحد 'z' = 122. لو طرحت 97 تاخد 0 لـ 25، يعني index جاهز. في C++ بتكتب c - 'a'، لكن في JS 'c' - 'a' بتطلع NaN. (الكبيرة بتبدأ من 65، والأرقام من 48.)
  4. كل حرف بيزوّد خانته. O(1) لكل حرف، فالكل O(n).
  5. الرجوع من index لحرف: String.fromCharCode(97 + i). ولاحظ إن اللف على الـ 26 خانة بيطلّع الحروف مترتبة أبجديًا ببلاش.
ده hash map صغير الـ array دي في الحقيقة hash map: الـ key هو الحرف، والـ hash function هي 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] هي الخانة. الصف الأول، بعدين العمود، دايمًا.

  1. عدد الصفوف = عدد الـ arrays اللي جوه. عدد الأعمدة = طول صف واحد. ده بيفترض إن فيه صف واحد على الأقل، فلو الـ grid ممكن تبقى فاضية، اعمل check الأول.
  2. -Infinity مش 0: لو كل المجاميع سالبة، الـ 0 هيطلع إجابة مش موجودة أصلًا.
  3. الـ rowSum بيتعرّف جوه الـ loop البراني، فبيرجع 0 مع كل صف. لو عرّفته برا، المجاميع هتتراكم من صف للتاني.
  4. grid[r][c]، مش grid[c][r]. لو الـ matrix مش مربعة وعكستهم، هتقرا برا الحدود وتاخد undefined.
  5. الـ update بعد ما الصف يخلص. لو حطيته جوه الـ loop الجوانية هتقارن مجاميع ناقصة، ومع أرقام سالبة الإجابة هتطلع غلط.

الوقت O(rows × cols): كل خانة بتتزار مرة. وتلات حاجات هتحتاجهم كتير:

لو لفّيت عمود عمود، الـ loop البرانية بقت على c، بس الوصول لسه grid[r][c]. وشرط الحدود ده هتكتبه في كل مسألة grid لما تبص على الجيران. الـ matrix كـ graph (جزر، flood fill، BFS) ليها فصل لوحدها: Graphs على Grid.

كده الأدوات كلها معاك. يلا نستخدمها، وأول مسألة بتجمع الـ shifting مع اللف من الآخر.

مثال محلول 1: Merge Sorted Array

Merge Sorted Array

easyLeetCode 88

عندك nums1 فيها m رقم حقيقي مترتبين، وبعدهم n صفر مجرد أماكن فاضية. و nums2 فيها n رقم مترتبين. ادمج الاتنين جوه nums1 نفسها، والنتيجة كلها تبقى مترتبة. مفيش return.

Input: nums1 = [1, 3, 7, 9, 0, 0, 0], m = 4, nums2 = [2, 4, 8], n = 3 Output: nums1 = [1, 2, 3, 4, 7, 8, 9] Input: nums1 = [0], m = 0, nums2 = [5], n = 1 Output: nums1 = [5]

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

  1. افهم المطلوب: الإجابة لازم تتكتب جوه nums1، والأصفار اللي في آخرها هي المكان المتاح.
  2. Brute force: حط nums2 في الأصفار واعمل sort: O((m+n) log(m+n)). شغال، بس رامي معلومة إن الاتنين مترتبين.
  3. Merge عادي من الأول في array جديدة: O(m+n)، بس محتاج O(m+n) memory. ولو عملته من الأول جوه nums1 نفسها، هتكتب فوق أرقام لسه ما قريتهاش. شوف بنفسك:
  1. الـ key insight: الأماكن الفاضية في الآخر. فلو ملينا من الآخر بالأكبر، عمرنا ما هنكتب فوق حاجة لسه محتاجينها. نفس قاعدة الـ insert: اللف عكس اتجاه النقل.
  2. الخطة: i على آخر رقم حقيقي في nums1، و j على آخر nums2، و k على آخر خانة. كل لفة: الأكبر من الاتنين يروح k.
  3. Edge cases: n = 0، m = 0، كل nums2 أصغر من nums1، وأرقام متساوية.
  1. m - 1 مش nums1.length - 1: آخر رقم حقيقي. اللي بعده أصفار ملهاش معنى.
  2. أكبر رقم في الاتنين مكانه آخر خانة أكيد، فبنبدأ نكتب من هنا.
  3. ليه j >= 0 بس؟ لو nums2 خلصت، اللي فاضل في nums1 في مكانه الصح أصلًا، فنقف. لو nums1 خلصت الأول، الشرط ده بيخلّينا نكمّل ننقل nums2.
  4. i >= 0 الأول عشان الـ short-circuit: لو i = -1 مش هنقرا nums1[-1] خالص. و > ولا >= مش فارقة هنا: في التساوي أي واحد فيهم صح.
  5. رقم nums1 أكبر، فبيتنقل لـ k، ومكانه القديم بقى فاضي ينفع نكتب فيه بعدين.
  6. رقم nums2 أكبر أو مساوي، فبينزل في k.
  7. كل لفة بتملا خانة واحدة بالظبط، فـ 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.

في الانترفيو قول الـ invariant بصوت عالي: "الـ k دايمًا قدّام i بـ j + 1 خانة، فعمري ما هكتب فوق رقم لسه محتاجه". الجملة دي هي الفرق بين إنك حافظ الحل وإنك فاهمه.

هنا الـ in-place كان سهل لأن فيه مكان فاضي. طب لو مفيش ولا خانة فاضية، وعايز تزحلق الـ array كلها؟

مثال محلول 2: Rotate Array

Rotate Array

mediumLeetCode 189

زحلق الـ array لليمين k خطوات in-place: كل عنصر يمشي k خانة يمين، واللي يطلع من الآخر يلف ويدخل من الأول. يعني آخر k عناصر بييجوا قدّام.

Input: nums = [1, 2, 3, 4, 5, 6, 7], k = 3 → [5, 6, 7, 1, 2, 3, 4] Input: nums = [1, 2, 3, 4, 5, 6, 7], k = 10 → [5, 6, 7, 1, 2, 3, 4] (10 % 7 = 3) Input: nums = [9, 8], k = 1 → [8, 9]

الجديد هنا إن مفيش ولا خانة فاضية زي Merge. الحل هيتبني كله على reverseRange اللي كتبناها فوق.

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

  1. Brute force: زحلق خطوة واحدة (O(n))، وكرّر k مرة: O(n · k). مع n و k لحد 10⁵ ده 10¹⁰، TLE.
  2. بـ array إضافية: العنصر اللي عند i مكانه الجديد (i + k) % n. O(n) وقت بس O(n) memory. قوله كبداية في الانترفيو.
  3. أول حاجة: k %= n. اللف n مرة بيرجّع الـ array زي ما هي، فـ k = 10 على 7 عناصر هي هي k = 3.
  4. الـ key insight: قسّم الـ array لجزئين: A أول n - k، و B آخر k. إحنا عايزين A B تبقى B A. وده بيتعمل بتلات reverses.
  5. Edge cases: k = 0، k أكبر من n أو مضاعف ليه، و n = 1.

ليه الخطوة 1 بتدّي rev(B) | rev(A)؟ لأن عكس الـ array كلها بيخلّي آخر عنصر أول عنصر. فالـ block اللي كان في الآخر (B) بيبقى في الأول، بس كل block جوه نفسه مقلوب. الخطوتين 2 و 3 بيصلّحوا القلبة دي، كل block لوحده، من غير ما يغيّروا مكانه.

  1. من غير الـ %: k = 10 على 7 عناصر هتخلّي الخطوة 2 تعكس من 0 لـ 9، فتقرا undefined من برا وتكبّر الـ array لـ 10 خانات. جرّبتها: النتيجة [undefined × 3, 1, 2, ...].
  2. الخطوة 1: A B بقت rev(B) rev(A).
  3. أول k خانات هما rev(B)، والـ k - 1 عشان الـ r inclusive. لو k = 0 بتبقى reverse(0, -1) والـ l < r بتمنع أي حاجة. تمام.
  4. من k لـ n - 1 هو rev(A)، وبعد العكس يرجع A.
  5. نفس 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

Longest Common Prefix

easyLeetCode 14

عندك array of strings. رجّع أطول بداية مشتركة بينهم كلهم. لو مفيش ولا حرف مشترك في الأول، رجّع "".

Input: ["coding", "codec", "code"] → "cod" Input: ["planet", "plane", "plan"] → "plan" Input: ["cat", "dog"] → ""

الجديد هنا إن بنلف على كذا string في نفس الوقت بنفس الـ index (عمود عمود)، وبنقطع النتيجة بـ slice.

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

  1. افهم المطلوب: الـ prefix المشترك لازم يكون بداية لكل كلمة، فهو مش ممكن يبقى أطول من أقصر كلمة.
  2. Horizontal: خد أول كلمة كـ prefix، وقصّرها مع كل كلمة لحد ما تبقى بداية ليها. شغال، بس بيعمل strings جديدة كتير.
  3. Vertical (الأوضح): بص على العمود i: الحرف رقم i في كل الكلمات. لو كلهم زي بعض، كمّل. أول ما عمود يختلف أو كلمة تخلص، الإجابة هي الحروف اللي قبل i.
  4. Edge cases: كلمة واحدة بس، كلمة فاضية، كل الكلمات زي بعض.
  1. أي حرف في الـ prefix لازم يكون في أول كلمة، فهي المرجع. أي كلمة تانية كانت تنفع برضه.
  2. i هو رقم العمود، وبيقف عند طول first لأن الـ prefix مش هيعدّيها.
  3. s بيبدأ من 1، لأن 0 هي first نفسها.
  4. سببين للوقوف: الكلمة خلصت (i === strs[s].length)، أو الحرف مختلف. في JS، strs[s][i] بعد الآخر بترجع undefined فالشرط التاني هيمسكها لوحده، بس اكتبها صريحة: أوضح، وفي لغات تانية القراية برا الحدود bug.
  5. early return بـ slice(0, i): الحروف من 0 لـ i - 1، وهي بالظبط الأعمدة اللي اتطابقت. الـ i نفسه هو أول عمود بايظ، فمش داخل.
  6. لو الـ 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) غير الإجابة.

حل تاني بيعجب الناس رتّب الكلمات، وقارن أول كلمة وآخر كلمة بس. الترتيب الأبجدي بيحط أكتر اتنين مختلفين في الطرفين، فالـ prefix المشترك بينهم هو المشترك بين الكل. أقصر في الكتابة، بس الـ sort بيضيف O(n log n) مقارنات.

هنا قرينا الـ strings بس من غير ما نبني حاجة. طب لو عايز تفكّك string لكلمات وتبني واحد جديد، والمسافات بايظة؟

مثال محلول 4: Reverse Words in a String

Reverse Words in a String

mediumLeetCode 151

اعكس ترتيب الكلمات في string (مش الحروف). الكلمة حروف ورا بعض من غير مسافة. ممكن يبقى فيه مسافات في الأول والآخر، أو أكتر من مسافة بين كلمتين. الإجابة كلمات بينهم مسافة واحدة بالظبط، ومن غير مسافات على الأطراف.

Input: " we can do " → "do can we" Input: " hello cairo world " → "world cairo hello" Input: "one" → "one"

الجديد هنا إن بنعمل parsing: نقطّع string لكلمات وسط مسافات زيادة، ونبني output جديد بـ parts + join.

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

  1. افهم المطلوب: المسافات الزيادة تختفي، والكلمات نفسها ما تتعكسش من جوه.
  2. في JS فيه one-liner: trim وبعدين split على أي عدد مسافات وبعدين reverse و join. O(n)، وده كويس تبدأ بيه.
  3. الـ interviewer هيقولك: من غير split. امشي بـ index من الآخر: فوّت المسافات، علّم آخر الكلمة، ارجع لحد المسافة اللي قبلها، واقطع الكلمة بـ slice. الكلمات بتطلع بالترتيب المعكوس لوحدها.
  4. Edge cases: مسافات في الأول والآخر، مسافات كتير ورا بعض، كلمة واحدة.
  1. من غير trim، الـ split هيطلّع '' في الأول أو الآخر: ' a b '.split(/\s+/) بتدّي ['', 'a', 'b', ''].
  2. /\s+/ معناها مسافة واحدة أو أكتر كـ separator. لو كتبت split(' ')، كل مسافتين ورا بعض هيطلّعوا string فاضي: ' a b'.split(' ') بتدّي ['', '', 'a', 'b'].
  3. reverse هنا على الـ array الجديدة اللي طلعت من الـ split، مش على s.
  4. join(' ') بمسافة واحدة. ولاحظ إن كل خطوة O(n)، فالكل O(n).
  1. بنبدأ من الآخر، فأول كلمة نلاقيها هي آخر كلمة. الترتيب المعكوس بييجي ببلاش من غير reverse.
  2. نفوّت أي مسافات. الـ i >= 0 الأول عشان ما نقراش برا الـ string.
  3. لو خلصنا وإحنا بنفوّت مسافات، يبقى مفيش كلمات تاني. من غير السطر ده هنعمل push لكلمة فاضية، والنتيجة هتطلع "do can we " بمسافة زيادة في الآخر (جرّبتها).
  4. end هو آخر حرف في الكلمة. بعدين i بيرجع لحد ما يقف على المسافة اللي قبل الكلمة، أو -1 لو الكلمة في أول الـ string.
  5. i + 1 لأن i واقف على المسافة، والكلمة بتبدأ بعدها. و end + 1 لأن slice مش بياخد الـ end. يعني الكلمة من i + 1 لـ end شاملين.
  6. 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.

الـ follow-up المشهور "اعملها بـ O(1) extra space" في لغة الـ string فيها mutable زي C++: اعكس الـ string كله، وبعدين اعكس كل كلمة لوحدها. ده نفس trick الـ Rotate Array بالظبط: reverse للكل، وبعدين reverse لكل جزء. في JS مش هينفع حرفيًا، لأنك هتحتاج array of chars الأول.

دي الأدوات والأمثلة. قبل ما تتمرن، خد الغلطات اللي بتوقّع الناس في الحاجات دي بالذات.

غلطات مشهورة

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.

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

First Unique Character in a String

easyLeetCode 387

string فيه حروف lowercase بس. رجّع index أول حرف ما اتكررش خالص، ولو مفيش رجّع -1.

"swiss" → 1 ('w') "kayak" → 2 ('y') "aabb" → -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 دقيقة على واحدة، ارجع للجزء بتاعها هنا، وبعدين حاول تاني من غير ما تبص.

خلصتهم؟ خد الفصل كله في صفحة واحدة.

الخلاصة

في جملة واحدة الـ array خانات لازقة في بعض: القراية بالـ index ببلاش، وأي تغيير في الأول أو النص بيزحلق اللي بعده. فاختار اتجاه اللف اللي ما يكتبش فوق حاجة لسه محتاجها، وعدّل in-place بـ swap و reverse.
السؤالالإجابة
< ولا <=؟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).