إزاي تحل أي مسألةproblem-solving framework · understand → brute force → optimize → test

الفرق بين اللي بيحل واللي بيتلخبط مش الذكاء. الفرق إن الأول عنده steps ثابتة بيمشي عليها في كل مسألة، من أول ما يقرا لحد ما يدوس Submit. الفصل ده بيديك الـ steps دي، وبيقفل باب أشهر bug في الدنيا: الـ off-by-one.

قبله: ولا حاجة، ده أول فصل بيمهّد لـ: Big-O و JavaScript للانترفيو

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

  • تمشي على 8 steps ثابتة في أي مسألة، وتعرف إنت واقف في أنهي step.
  • تقرا الـ constraints وتعرف منها الـ complexity المطلوبة قبل ما تكتب سطر.
  • تعمل dry-run بـ trace table وتمسك الـ bug بإيدك قبل الـ judge.
  • تقفل باب الـ off-by-one: < ولا <=، و r - l + 1 ولا r - l، و length - 1.
  • تحل FizzBuzz و Missing Number و Best Time to Buy and Sell Stock بالـ steps كاملة، وتعرف تقول إيه وإنت بتحل.

ليه محتاج طريقة ثابتة؟

إنت حليت مسائل قبل كده، وأكيد حصلك الموقف ده. المسألة كانت FizzBuzz: لكل رقم من 1 لحد n، لو بيقبل القسمة على 3 اكتب Fizz، وعلى 5 اكتب Buzz، وعلى الاتنين FizzBuzz، وغير كده الرقم نفسه. وإنت كتبت:

مفيش error، والـ array شكلها مظبوط، بس الـ judge بيقول Wrong Answer. شوفه على n = 5:

"من 1 لحد n" معناها إن الـ n نفسها داخلة، والشرط i < n بيقف قبلها بخطوة. الـ fix حرف واحد: i <= n.

بس الدرس مش الحرف ده. المشكلة إن مفيش step في طريقتك بتمسك الغلطة دي. لو سألت نفسك "الـ n داخلة ولا لأ؟"، أو عملت dry-run على n = 5 وعدّيت العناصر، كنت هتلاقي 4 بدل 5 في أقل من دقيقة.

تشبيه الطيار اللي طاير ألف رحلة لسه بيمسك الـ checklist قبل كل إقلاع ويقرا بند بند. مش عشان مش فاهم، عشان الغلطات الكبيرة بتيجي من حاجات صغيرة الدماغ بيفوّتها وهو واثق. الـ steps دي هي الـ checklist بتاعتك.
  1. افهم: قول المسألة بكلامك، اسأل، واقرا الـ constraints.
  2. أمثلة: مثال صغير بإيدك، وبعدين الـ edge cases.
  3. Brute force: أبسط حل صح، حتى لو بطيء، والـ complexity بتاعته.
  4. حسّن: دوّر على الـ bottleneck والشغل المتكرر، واختار data structure.
  5. خطة: الـ steps كـ comments قبل الكود.
  6. كود: املا تحت كل comment.
  7. اختبر: dry-run بـ trace table على مثال صغير و edge case.
  8. حلّل: الـ time والـ space complexity وليه.

طب إمتى بالظبط ترجع للـ checklist دي؟ وتعمل إيه لو حاجة باظت؟

إمتى تستخدم الـ steps دي

ارجع للـ steps لما: أول ما تقرا المسألةإيدك راحت للكيبورد قبل ما تفهمWrong Answer Time Limit ExceededRuntime Errorشغال على المثال بسمش عارف تبدأ منينسكتّ في الانترفيو
ممكن تختصر لو: مسألة حليتها قبل كده وفاكرهاeasy واضحة من سطرين

حتى لما تختصر، ما تختصرش step 7 (الـ dry-run). المسائل اللي إنت واثق منها هي بالظبط اللي بيعدّي فيها off-by-one.

الـ stepبيطلع منها إيهوقتها في انترفيو 45 دقيقة
1. افهمسطر input → output، و target complexity3 لـ 5 دقايق
2. أمثلة3 لـ 5 أمثلة بإجاباتها2 لـ 3 دقايق
3. Brute forceفكرة + complexity2 لـ 3 دقايق
4. حسّنفكرة أسرع + complexity5 لـ 10 دقايق
5 و 6. خطة وكودحل كامل12 لـ 17 دقيقة
7. اختبرbugs اتمسكت5 دقايق
8. حلّلجملتين1 دقيقة
اللي حصلارجع لـليه
Wrong Answerstep 7، وبعدين 2غالبًا edge case ما جرّبتهوش، أو off-by-one.
TLEstep 1، وبعدين 4الـ complexity أكبر من اللي الـ constraints تسمح بيه، أو فيه hidden cost (Big-O).
Runtime Errorstep 2input فاضي، index برا الـ array، أو recursion عميقة.
مش عارف تبدأstep 2، وبعدين 3حل مثال صغير بإيدك وراقب دماغك بيعمل إيه.
flowchart TD
  A["1 Understand: restate, ask, read constraints"] --> B["2 Examples by hand + edge cases"]
  B --> C["3 Brute force + its Big-O"]
  C --> D{"Fast enough for the constraints?"}
  D -- no --> E["4 Optimize: bottleneck, repeated work, data structure"]
  E --> D
  D -- yes --> F["5 Plan as comments"]
  F --> G["6 Code"]
  G --> H["7 Dry-run with a trace table"]
  H --> I{"Matches the expected output?"}
  I -- no --> G
  I -- yes --> J["8 Say time and space complexity"]
  

الـ steps فيها loop-تين: لو الحل بطيء ترجع تحسّن، ولو الـ dry-run طلّع غلطة ترجع للكود.

نبدأ من step 1: إزاي تتأكد إنك فاهم المسألة صح قبل أي حاجة؟

Step 1: افهم المسألة

أكتر وقت بيضيع مش في الكود. بيضيع في إنك تحل مسألة غير اللي اتسألت. فالـ step دي ليها 3 أجزاء:

أ) قولها بكلامك في سطر

اكتب فوق الكود: in: array of n numbers → out: index of .... لو مش عارف تكتبه، يبقى لسه ما فهمتش. ودوّر على التفاصيل اللي بتغيّر كل حاجة:

ب) اسأل clarifying questions

تشبيه الميكانيكي الشاطر ما بيفكّش العربية أول ما تقوله "فيه صوت". بيسأل: إمتى؟ وإنت ماشي ولا واقف؟ في السرعة العالية بس؟ كل سؤال بيشيل نص الاحتمالات قبل ما يمسك مفتاح.

في الانترفيو الأسئلة دي متوقعة منك. وفي LeetCode إجاباتها في الـ constraints، فاقراها بنفس الأسئلة:

السؤالبيغيّر إيه
Can the input be empty?محتاج check في الأول، والـ init ممكن يبوظ.
Negatives? Zeros? Duplicates?max = 0 بيبوظ مع السالب، والتكرار بيغيّر العدّ.
Is the array sorted?لو آه، غالبًا two pointers أو binary search.
Return indices or values?لو indices، الـ sort بيضيّعها.
Can I modify the input?sort() بيعدّل الأصلي.
How large can n and the values get?بيحدد الـ complexity، وهل فيه overflow.

ج) الـ constraints بتقولك الـ complexity

السطر اللي زي 1 <= nums.length <= 10⁵ مش ديكور، ده أهم سطر في المسألة. القاعدة: السيرفر بيعمل حوالي 10⁸ عملية بسيطة في الثانية. فاحسب الـ brute force هيعمل كام عملية مع أكبر n:

لو n لحدالمسموح تقريبًامعناها
20O(2ⁿ)جرّب كل الاحتمالات، عادي.
500O(n³)تلات loops جوه بعض.
5,000O(n²)loop جوه loop.
10⁵ لـ 10⁶O(n log n) أو O(n)nested loops = TLE. محتاج sort أو hash map أو one pass.
10⁹O(log n) أو O(1)حتى loop واحدة = TLE.

التفاصيل في Big-O. المهم إنك تعرف الـ target قبل ما تفكّر في الحل.

في الانترفيو ابدأ بـ "So I get ..., and I return .... Let me ask a couple of questions first." وكل إجابة اكتبها comment فوق الكود.

فهمت المطلوب. بس على أنهي input هتجرّب حلّك؟

Step 2: أمثلة بإيدك و edge cases

أمثلة المسألة دايمًا "happy path"، والـ judge عنده tests مستخبية عكسها بالظبط. فبتعمل حاجتين:

  1. مثال صغير تحله بإيدك: 4 لـ 6 عناصر، على ورقة، من غير كود. وراقب دماغك بيعمل إيه: بيدوّر على إيه؟ بيفتكر إيه؟ ده أول draft للـ algorithm.
  2. قائمة edge cases كـ comments، ترجعلها في step 7.
الحالةمثالبتكسر إيه غالبًا
فاضي[] "" n = 0nums[0] = undefined.
عنصر واحد[5]أي مقارنة بالجيران.
كله زي بعضه[3, 3, 3]< مقابل <=، والتكرار.
سالب وأصفار[-3, 0, -1]max = 0، والضرب في صفر.
مترتب / بالعكس[1, 2, 3] [3, 2, 1]الإجابة في أول أو آخر عنصر.
مفيش إجابةtarget مش موجودنسيت الـ return بعد الـ loop.
أكبر حجمn = 10⁵TLE، والـ recursion العميقة.
مش لازم كلهم اختار 2 أو 3 مرتبطين بالمسألة: فيها max؟ جرّب السالب. فيها جيران؟ جرّب عنصر واحد. فيها range؟ جرّب أصغر n.

عندك أمثلة بإجاباتها. أول حل تكتبه يبقى إيه؟

Step 3: Brute force الأول

ناس كتير بتتكسف من الحل البطيء وبتدوّر على الذكي على طول. وده غلط لأن الـ brute force:

مثال: مسألة البورصة (هنحلها كاملة تحت). سعر سهم كل يوم، تشتري في يوم وتبيع في يوم بعده، وعايز أكبر مكسب. الـ brute force: لكل يوم بيع، جرّب كل أيام الشرا اللي قبله:

حوالي n²/2 زوج. مع n = 10⁵ يبقى 5 × 10⁹ عملية، حوالي 50 ثانية: TLE. بس دلوقتي معاك حاجة صح تبني عليها. ولما تكتب الحل السريع، الـ brute force بيراجعه:

ليه inputs صغيرة؟ عشان لو فيه bug، يظهرلك على 3 أرقام تقدر تعمل عليهم dry-run بإيدك.

في الانترفيو قوله في جملة مع الـ complexity وليه مش كفاية: "The brute force tries every pair, that's O(n²), about 10¹⁰ for n = 10⁵. Too slow, so let me see what work is repeated."

الـ brute force بطيء. إزاي تلاقي الأسرع بنظام، مش بالحظ؟

Step 4: حسّن

مفيش سحر. فيه 3 أسئلة بتسألهم للـ brute force بالترتيب:

  1. فين الـ bottleneck؟ غالبًا الـ loop الداخلية: هي اللي بتحوّل O(n) لـ O(n²). ركّز عليها.
  2. فيه شغل بيتكرر؟ الـ loop الداخلية بتحسب حاجة، وفي اللفة الجاية بتحسبها تاني من الأول تقريبًا؟ احفظها في متغير وحدّثها. في البورصة: الـ loop الداخلية بتدوّر على أقل سعر قبل يوم البيع، ولما يوم البيع يتحرك خطوة، الـ min ده بيتغيّر بعنصر واحد بس.
  3. السؤال اللي بيتكرر كل لفة إيه؟ لو سؤال بسيط، غالبًا فيه data structure بتجاوبه في O(1) أو O(log n).
السؤال اللي بيتكررالأداةالفصل
"الرقم ده شفته قبل كده؟"SetHash Map و Set
"شفته كام مرة؟ أو فين؟"MapHash Map و Set
"أصغر أو أكبر حاجة so far؟"متغير واحدمثال 3 تحت
"مجموع العناصر من l لـ r؟"prefix sumPrefix Sum
"فيه زوج مجموعه X في array مترتبة؟"two pointersTwo Pointers
"أطول جزء متصل بشرط؟"sliding windowSliding Window
"أول مكان الشرط بيبقى فيه true؟"binary searchBinary Search
"آخر حاجة اتفتحت وما اتقفلتش؟"stackStack
"أصغر حاجة من مجموعة بتتغير؟"heapHeap

وسؤال رابع بيوفّر وقت: إيه أحسن حل ممكن أصلًا؟ لو لازم تقرا كل عنصر عشان تجاوب، مفيش أسرع من O(n). فلو وصلت O(n)، ما تضيّعش وقت تدوّر على أحسن.

الـ sort بيفتح أبواب لو الترتيب الأصلي مش مهم، جرّب ترتّب الأول. O(n log n)، وبعدها two pointers و binary search بيبقوا ممكنين، والمتكرر بيبقى جنب بعضه.

لقيت الفكرة. قبل ما تكتب: إزاي ترتّبها عشان الكود يطلع صح من أول مرة؟

Step 5 و 6: الخطة كـ comments، وبعدين الكود

وإنت بتكتب كود، دماغك شايل حاجتين: الـ algorithm والـ syntax. والـ comments بتخلّيك تخلص من الأول قبل التاني. وفي الانترفيو الـ interviewer بيشوف الخطة ويقولك لو فيها مشكلة قبل 10 دقايق كود. ده القالب اللي تفتح بيه أي مسألة:

  1. سطر input → output. لو مش عارف تكتبه، ارجع اقرا تاني. ده أرخص وقت تكتشف فيه إنك فاهم غلط.
  2. الأسئلة وإجاباتها. لما تيجي تكتب، هتفتكر إن فيه سالب فمش هتكتب max = 0.
  3. الـ target complexity. بيمنعك تضيّع وقت في حل عارف إنه هياخد TLE.
  4. الأمثلة بالإجابات المتوقعة. من غيرها الـ dry-run ملوش لازمة، لأنك مش هتعرف تقارن بإيه.
  5. الـ brute force والفكرة الأحسن، كل واحد في سطر. لو الفكرة مش بتتقال في جملة، لسه مش واضحة.
  6. الـ state: شايل إيه معاك وإنت ماشي، وقيمته الأولى إيه. نص الـ bugs بتيجي من القيمة الأولى: 0 ولا -Infinity ولا nums[0].
  7. إيه اللي بيحصل لكل عنصر. لو الإجابة فيها "وارجع لكل اللي فات"، ده O(n²) مستخبي.
  8. إيه اللي بيترجع. ساعات المتغير نفسه، وساعات حاجة محسوبة منه.
  9. الـ dry-run والـ complexity بعد الكود. والـ complexity دايمًا مع السبب.

ولما تملاه لمسألة البورصة، كل comment تحته سطر كود تقريبًا:

وإنت بتملا: أسامي واضحة (minPrice مش a)، وhelper function لأي حتة ليها اسم (isAlnum(ch)، inBounds(r, c))، وما تحسّنش وإنت بتكتب: اكتب اللي اتفقت عليه بالظبط.

الكود اتكتب. إزاي تتأكد إنه صح قبل ما الـ judge يقولك؟

Step 7: Dry-run بـ trace table

الـ dry-run إنك تبقى إنت الكمبيوتر: تمشي على الكود سطر سطر بمثال صغير، وتكتب قيمة كل متغير بعد كل لفة. والورقة دي اسمها trace table: column لكل متغير، و row لكل لفة.

تشبيه زي ما بتراجع فاتورة السوبر ماركت بند بند بالقلم. ما بتبصش على الرقم اللي في الآخر وتقول "شكله مظبوط"، بتمشي سطر سطر لحد ما تلاقي البند اللي اتحسب غلط.

الـ function دي بتجيب أكبر رقم. بتشتغل على [4, 9, 2] وبتطلّع 9:

  1. هنا الـ bug. max = 0 معناها إنك افترضت إن فيه رقم ≥ 0، والمسألة ما قالتش كده. لو كله سالب، الـ function هترجّع 0، وده مش موجود في الـ array أصلًا.
  2. loop على كل index من 0 لـ length - 1. الـ < صح هنا.
  3. لو الرقم الحالي أكبر من أكبر رقم so far، يبقى هو الأكبر الجديد.
  4. وعلى array فاضية بترجّع 0، وده كمان محتاج قرار: المسألة عايزة إيه هنا؟

المثال العادي مش هيكشفها. dry-run على edge case من الجدول: كله سالب.

الـ trace table بيّنت المشكلة في 3 rows: max عمره ما اتغيّر. الـ fix: قيمة أولى أي رقم حقيقي يكسبها:

الكود صح. فاضل تقول هو سريع قد إيه.

Step 8: قول الـ complexity وليه

إنت حسبتها في step 3 و 4، دلوقتي بتأكّدها على الكود الفعلي:

وقولها مع السبب: "O(n) time because each price is visited once, O(1) space because I only keep two numbers." الفصل الجاي Big-O كله عن الـ step دي.

الـ dry-run بيمسك bugs كتير، بس فيه نوع واحد بيرجع تاني وتالت مهما اتعلّمت: الفرق بواحد.

Off-by-one: الغلطة اللي بتيجي بفرق واحد

الـ loop بتلف مرة زيادة أو ناقصة، أو العدّ بيطلع ±1. ما بتضربش error، والناتج قريب من الصح، فبتعدّي من عينك. الجزء ده بيديك قواعد تبطّل بيها تخمين.

أ) الـ range شامل ولا لأ؟

كل طرف في الـ range يا داخل (inclusive) يا برا (exclusive). [1, n] الاتنين داخلين، و [0, n) البداية داخلة والنهاية برا:

الكلام في المسألةالـ rangeالـ loopبتلف كام مرة
"على كل عنصر في الـ array"[0, n)for (let i = 0; i < n; i++)n
"الأرقام من 1 لحد n"[1, n]for (let i = 1; i <= n; i++)n
"الأرقام من 0 لحد n"[0, n]for (let i = 0; i <= n; i++)n + 1
"من الآخر للأول"[n - 1 ... 0]for (let i = n - 1; i >= 0; i--)n
"كل عنصر مع اللي قبله"[1, n)for (let i = 1; i < n; i++)n - 1

القاعدة اللي بتعدّ بيها من غير ما تعدّ: for (i = a; i < b; i++) بتلف b - a مرة، و for (i = a; i <= b; i++) بتلف b - a + 1. شوف 4 loops شبه بعض على n = 5:

الـ key insight: loop C (i = 1; i < n) هي bug الـ FizzBuzz، بس هي هي الصح لو بتقارن كل عنصر باللي قبله، لأن أول عنصر مالوش حد قبله. مفيش loop "صح" و loop "غلط"، فيه loop مناسبة للـ range المطلوب.

ب) عدد العناصر ولا المسافة؟

تشبيه ركبت المترو من محطة رقم 3 ونزلت في 7. القطر عدّى 4 مسافات بين محطات. بس لو عدّيت المحطات نفسها، شامل اللي ركبت منها واللي نزلت فيها، هتلاقيهم 5. سؤالين مختلفين، والفرق واحد.
السؤالالمعادلةl = 3، r = 7بيظهر فين
عدد العناصر في [l, r]r - l + 15طول window في sliding window
المسافة من l لـ rr - l4العرض في Container With Most Water
عدد العناصر في [l, r)r - l4slice(l, r)
عدد العناصر بين l و rr - l - 13Trapping Rain Water بالـ stack

مش متأكد؟ جرّب l = r = 3: عدد العناصر لازم 1 (3 - 3 + 1)، والمسافة لازم 0 (3 - 3). الحالة الصغيرة بتختبر المعادلة في ثانية.

ج) length - 1 والـ half-open range

آخر index هو length - 1. وفي JS، nums[nums.length] مش crash زي C++ ممكن يعمل: بترجّع undefined بهدوء، وأي حساب بيها NaN، وأي مقارنة مع NaN false. فالـ bug بيمشي ساكت.

والـ half-open [l, r) (اللي i < n و slice بيستخدموه) بيقلّل الـ off-by-one: الطول r - l من غير +1، والـ range الفاضي هو l === r، والتقسيم نضيف: [l, m) + [m, r) = [l, r) من غير تكرار ولا فراغ.

القاعدة: 3 أسئلة وأصغر n

  1. بتبدأ منين؟ 0؟ 1؟ i + 1؟
  2. النهاية داخلة؟ ده اللي بيقرر < ولا <=.
  3. بتلف كام مرة؟ بالقاعدة، وقارن باللي المسألة عايزاه.

وبعدين جرّب في دماغك n = 1 و n = 0. ده الملخص في كود واحد:

  1. الأشهر: من 0 لأن أول index صفر، و < لأن آخر index n - 1. بتلف n مرة.
  2. لما المسألة بتتكلم عن أرقام مش indices: البداية 1 والنهاية داخلة، فـ <=.
  3. من n - 1 (مش n)، و >= 0 عشان index صفر يتعالج. > 0 هتفوّت أول عنصر.
  4. من 1 لأن أول عنصر مالوش حد قبله. ولو بتقارن بـ nums[i + 1] بدل nums[i - 1]، الشرط يبقى i < n - 1.
  5. الـ +1 عشان العنصر اللي عند l نفسه بيتحسب. المسافة بتعدّ الخطوات مش النقط.
  6. من l لـ r - 1. لو عايز لحد r شامل: slice(l, r + 1).

كده معاك الـ steps والـ bug الأشهر. فاضل اللي الانترفيو بيركّز عليه: بتقول إيه وإنت بتحل؟

إزاي تتكلم وإنت بتحل

الـ interviewer بيقيّم طريقة تفكيرك، وما يقدرش يشوفها إلا لو قلتها. 5 دقايق سكوت وبعدين كود كامل بتقلقه أكتر من حل بطيء متشرح كويس.

تشبيه سواق التاكسي الكويس بيقولك قبل ما يتحرك: "هطلع الكوبري وألف من التحرير". لو إنت عارف إن الكوبري واقف، تقوله بدري. الـ interviewer هو الراكب ده: لما تقول خطتك، يقدر يوجّهك قبل ما تمشي في طريق غلط.
الـ stepجملة تقولها
1. افهم"Let me restate it: I get ..., I return .... Can the array be empty? Can values be negative?"
2. أمثلة"Let me try a small example by hand: [7, 1, 5] ..."
3. Brute force"The straightforward way is every pair. That's O(n²), too slow for 10⁵."
4. حسّن"The inner loop keeps recomputing the minimum. I can keep it in a variable."
5. خطة"Here's the plan before I code: ... Does that sound good?"
6. كود"I start min at Infinity so the first price replaces it."
7. اختبر"Let me trace [7, 1, 5] ... and check one element, and decreasing prices."
8. حلّل"O(n) time, one pass. O(1) space, two variables."

جملة step 4 هي أهم جملة: بتسمّي الشغل المتكرر بالاسم. ولو وقفت:

نطبّق الـ steps كلها على 3 مسائل. كل واحدة بتضيف فكرة جديدة على اللي قبلها.

مثال محلول 1: FizzBuzz

Fizz Buzz

easyLeetCode 412

رجّع array فيها n string. العنصر رقم i (لكل i من 1 لـ n) يبقى "FizzBuzz" لو i بيقبل القسمة على 3 و 5، و "Fizz" لو على 3 بس، و "Buzz" لو على 5 بس، وغير كده الرقم كـ string.

Input: n = 5 → ["1", "2", "Fizz", "4", "Buzz"] Input: n = 1 → ["1"] Input: n = 15 → [..., "14", "FizzBuzz"]

هنا مفيش optimization. الفكرة كلها في step 1 و 2: الـ range وترتيب الشروط.

  1. افهم: in: n → out: n strings. "من 1 لحد n" يعني [1, n]، n عنصر بالظبط. والإجابة strings: "7" مش 7. الـ constraint n <= 10⁴، فـ O(n) تمام.
  2. أمثلة: n = 1 (لازم عنصر واحد)، n = 5، و n = 15 اللي بيختبر ترتيب الشروط.
  3. Brute force = الحل: loop وكام if. O(n)، ومفيش أسرع لأن الإجابة نفسها n عنصر.
  4. الخطة: loop من 1 لـ n شامل، الشرط الأخص الأول (15)، بعدين 3، بعدين 5، بعدين الرقم.
  1. const لأن الاسم مش هيشاور على array تانية. الـ push بيعدّل جواها، وده مسموح.
  2. أهم سطر. البداية 1 لأن العدّ من 1، و <= لأن n داخلة. عدد اللفّات n - 1 + 1 = n. جرّب n = 1: 1 <= 1، فبتلف مرة. تمام.
  3. ليه 15 الأول؟ أي مضاعف لـ 15 مضاعف لـ 3 كمان. لو شرط الـ 3 الأول، الـ 15 هيدخل فيه ويطلع "Fizz". القاعدة في if / else if: الأخص الأول.
  4. لو وصلنا هنا يبقى مش مضاعف لـ 15. فلو على 3، يبقى على 3 بس، ونفس الكلام لـ 5.
  5. String(i) لأن الإجابة strings. push(i) هيحط رقم، والـ judge هيقارن "7" بـ 7: Wrong Answer.
  6. الـ return بعد الـ loop، مش جواها.
Inputالمتوقعليه الحالة دي مهمة
n = 1["1"]مع i < n كانت هتطلع [].
n = 3["1","2","Fizz"]آخر عنصر هو الـ Fizz: لو n مش داخلة يضيع.
n = 15[..., "FizzBuzz"]لو 3 قبل 15، هيطلع "Fizz".

التعقيد: O(n) وقت. والـ memory O(n) بس دي الإجابة نفسها، وغيرها O(1).

في الانترفيو FizzBuzz بتتسأل عشان يشوفوا بتقرا الـ range صح وبترتّب الشروط صح. قول: "1 to n inclusive, so i <= n. And 15 first, because a multiple of 15 is also a multiple of 3."

FizzBuzz ما فيهاش step 4. المسألة الجاية فيها brute force بطيء لازم يتحسّن.

مثال محلول 2: Missing Number

Missing Number

easyLeetCode 268

array فيها n رقم مختلفين، كلهم من [0, n]. الـ range ده فيه n + 1 رقم، فواحد ناقص. رجّعه.

Input: [3, 0, 1] → 2 Input: [0, 1] → 2 (n = 2, so 2 is in the range) Input: [9, 6, 4, 2, 3, 5, 7, 0, 1] → 8

الجديد هنا: step 4 كاملة. الـ brute force O(n²)، وهنحسّنه مرتين: مرة بـ data structure، ومرة بفكرة بتشيل الـ memory الزيادة.

  1. افهم: أول trap في الـ range: [0, n] فيه n + 1 رقم. لو الطول 2، الممكن 0 و 1 و 2، فـ [0, 1] إجابتها 2.
  2. أمثلة: الناقص في النص ([3, 0, 1])، هو n ([0, 1])، هو الصفر ([1] → 0).
  3. Brute force: لكل رقم من 0 لـ n، includes. والـ includes loop مستخبية، فده O(n²).
  4. تحسين 1، السؤال المتكرر: "الرقم ده موجود؟" ده سؤال Set. O(n) وقت بس O(n) memory. (أو sort وأول nums[i] !== i: O(n log n).)
  5. تحسين 2، الـ key insight: إحنا عارفين المجموع لو مفيش ناقص: 0 + 1 + ... + n = n(n + 1)/2. اطرح مجموع الـ array، والفرق هو الناقص. O(n) وقت و O(1) memory.

لاحظ الـ off-by-one: الـ loop على x بـ <= لأن الـ range [0, n]. وفي حل الـ sort، لو مفيش حاجة ناقصة جوه، يبقى الناقص n نفسه، وده الـ return a.length. من غيره [0, 1] بترجّع undefined.

  1. طول الـ array هو نفسه أكبر رقم في الـ range: n رقم من n + 1 احتمال.
  2. مجموع 1..n هو n(n + 1)/2، والصفر مش بيزوّد. ليه n مش n - 1؟ لأن الـ range بيوصل لـ n شامل. والقسمة على 2 دايمًا صحيحة، لأن واحد من n و n + 1 زوجي.
  3. for...of لأننا مش محتاجين index، فأقل فرصة لـ off-by-one.
  4. الفرق = الرقم اللي ما اتجمعش.
حل تالت بـ XOR a ^ a = 0 و a ^ 0 = a. فلو عملت XOR لكل الأرقام من 0 لـ n ومعاهم عناصر الـ array، كل موجود بيلغي نفسه والناقص بيفضل. ميزته إنه مفيش جمع كبير، فمفيش overflow في C++. التفاصيل في Bit Manipulation.
Inputالمتوقعليه
[0, 1]2الناقص هو n نفسه.
[1]0الناقص هو الصفر.
[3, 0, 1]2في النص، ومش مترتبة.

التعقيد: O(n) وقت و O(1) memory، وده أحسن ممكن لأن لازم تشوف كل رقم.

في الانترفيو قول الحلول بالترتيب: "includes is O(n²). A Set gives O(n) time but O(n) space. The sum formula gives O(n) time and O(1) space." ولو سألك عن الـ overflow: في JS الأرقام مضبوطة لحد حوالي 2⁵³ والمجموع هنا حوالي 5 × 10⁷، ولو int 32-bit، الـ XOR بيحلها.

هنا التحسين جه من فكرة رياضية. في المسألة الجاية بييجي من حاجة أعم: شيل الشغل اللي بيتكرر.

مثال محلول 3: Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock

easyLeetCode 121

prices[i] سعر سهم في اليوم i. عملية واحدة: تشتري في يوم، وتبيع في يوم بعده. رجّع أكبر مكسب، أو 0 لو مفيش مكسب.

Input: [7, 1, 5, 3, 6, 4] → 5 (buy at 1, sell at 6) Input: [7, 6, 4, 3, 1] → 0 (prices only go down) Input: [2, 4, 1] → 2 (not 4 - 1: the 1 comes after the 4)

الجديد هنا: الـ optimization بيشيل loop كاملة عن طريق state بيتحدّث وإحنا ماشيين (running min). ده pattern هتشوفه في نص المسائل الجاية.

  1. افهم: max(prices[sell] - prices[buy]) بشرط buy < sell. و"رجّع 0" يعني إن مش تشتري خالص مسموح. الـ constraint n <= 10⁵: O(n²) = TLE.
  2. أمثلة: أسعار نازلة (0)، يوم واحد (0)، و [2, 4, 1] اللي بيكسر فكرة "أكبر سعر ناقص أصغر سعر": 4 - 1 = 3، بس الـ 1 جه بعد الـ 4. الإجابة 2.
  3. Brute force: كود step 3 فوق: O(n²).
  4. الـ key insight: لما يوم البيع ثابت، أحسن شرا هو أرخص يوم قبله. فالـ loop الداخلية كلها بتحسب min(prices[0..sell - 1])، ولما sell يزيد، الـ min بيتغيّر بعنصر واحد. نشيله في minPrice ونحدّثه، والـ loop الداخلية تختفي.
  1. ليه Infinity مش 0؟ مع 0، مفيش سعر أقل منه، فالمكسب هيتحسب كأنك اشتريت ببلاش. نفس bug الـ findMax بالعكس. prices[0] صح برضه لو الـ array مش فاضية.
  2. 0 مش -Infinity، لأن "ما اشترتش" مسموح ومكسبه صفر. مع -Infinity والأسعار نازلة هترجّع سالب.
  3. أرخص سعر شامل النهارده. لو النهارده هو الأرخص، السطر الجاي هيحسب price - price = 0، كأنك اشتريت وبعت في نفس اليوم، وده مش بيضر. ولو بدّلت السطرين، الحل برضه صح.
  4. لو بعت النهارده، أحسن شرا هو minPrice. ده بالظبط اللي الـ loop الداخلية كانت بتحسبه، بس في O(1).
Inputالمتوقعليه
[7, 6, 4, 3, 1]0نازلة: best لازم يفضل 0.
[5]0مفيش يوم بعده.
[2, 4, 1]2بيكسر max - min.
[3, 3, 3]0كله زي بعضه.

التعقيد: O(n) وقت، one pass. O(1) memory.

في الانترفيو "For each day, if I sell today, the best buy is the cheapest day before it. So I keep a running minimum instead of recomputing it." وبعدين اذكر [2, 4, 1] كمثال على ليه max - min غلط.

شفنا الـ steps وهي ماشية صح. الجاي: الغلطات اللي بتحصل لما تتنط على step.

غلطات مشهورة

كلها ما بتضربش error، بتطلّع إجابة قريبة من الصح. وده اللي بيخلّيها خطيرة.

1. < بدل <= في range شامل

الصح i <= n. اسأل "النهاية داخلة؟"، وعدّ: b - a لـ <، و b - a + 1 لـ <=.

2. قيمة أولى بتفترض حاجة

الصح -Infinity للـ max و Infinity للـ min، أو أول عنصر.

3. return في الـ else جوه الـ loop

"لقيت" ينفع تقولها من أول عنصر. "مش موجود" ما تقولهاش إلا بعد ما تشوف كل العناصر، يعني بعد الـ loop.

4. nums[i + 1] في loop لحد n

أي رقم !== undefined بيطلع true، فبيعدّ تغيير مش موجود. الصح i < nums.length - 1، أو تبدأ من 1 وتقارن بـ nums[i - 1].

5. عدّلت الـ input وإنت مش واخد بالك

لو المسألة ما قالتش in-place: [...nums].sort(...). وفي الانترفيو اسأل: "Can I modify the input?"

6. الحل الذكي قبل ما يبقى معاك حل صح

20 دقيقة على فكرة ذكية مش شغالة، والـ interviewer لسه ما شافش ولا حل. قول الـ brute force في دقيقة الأول، وبعدين حسّن. لو الوقت خلص، معاك حاجة.

جرّب نفسك على الأفكار دي.

اختبر نفسك

for (let i = 2; i <= 9; i++) بتلف كام مرة؟

  • 7
  • 8
  • 9
  • 10

النهاية داخلة، فـ 9 - 2 + 1 = 8. لو i < 9 كانت 9 - 2 = 7.

subarray من index 3 لـ index 7 (الاتنين داخلين). فيها كام عنصر؟

  • 4
  • 5
  • 6
  • 7

r - l + 1 = 5: 3، 4، 5، 6، 7. الـ 4 هي المسافة، زي مسافات المترو.

[10, 20, 30, 40, 50, 60].slice(2, 5) بترجّع كام عنصر؟

  • 3
  • 4
  • 5
  • 2

half-open: من 2 لـ 4، والـ 5 برا. 5 - 2 = 3: [30, 40, 50].

الـ constraint n <= 10⁵، وأول حل جالك nested loop على كل الأزواج. تعمل إيه؟

  • تدوس Submit، يمكن يعدّي
  • تقوله كـ brute force (حوالي 10¹⁰، TLE) وتدوّر على الشغل المتكرر في الـ loop الداخلية
  • تسيب المسألة
  • تكتبه بـ forEach عشان يبقى أسرع

10¹⁰ على 10⁸ في الثانية = حوالي 100 ثانية. بس الـ brute force هو اللي هيوريك الشغل المتكرر. وتغيير شكل الـ loop مش بيغيّر الـ complexity.

في Missing Number، الـ array طولها 4. الأرقام الممكنة إيه؟

  • من 0 لـ 3
  • من 1 لـ 4
  • من 0 لـ 4: خمس أرقام وواحد ناقص
  • من 1 لـ 5

[0, n] شامل فيه n + 1 رقم. عشان كده المعادلة n(n + 1)/2.

ليه "أكبر سعر ناقص أصغر سعر" غلط في Best Time to Buy and Sell Stock؟

  • عشان بطيء
  • عشان أصغر سعر ممكن ييجي بعد أكبر سعر، وما ينفعش تبيع قبل ما تشتري
  • عشان Math.max مش بتشتغل على arrays
  • مش غلط

[2, 4, 1]: max - min = 3، بس الـ 1 في آخر يوم. الصح 2. الـ running min بيحترم buy < sell تلقائي.

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

Find the Difference

easyLeetCode 389

t اتعمل من s بإنك لخبطت حروفه وزوّدت حرف واحد في أي مكان. رجّع الحرف الزيادة. امشي على الـ steps.

s = "abcd", t = "abcde" → "e" s = "", t = "y" → "y" s = "aab", t = "abaa" → "a" (the extra one can be a repeated letter)
تلميح 1

المثال التالت مهم: الحرف الزيادة ممكن يكون موجود في s. فـ "حرف في t مش في s" غلط، لازم تعدّ. Brute force: عدّ بـ Map وقارن، O(n).

تلميح 2

نفس فكرة Missing Number: المتوقع ناقص الموجود. كل حرف ليه رقم (charCodeAt). اجمع حروف t واطرح حروف s.

الحل

O(n) وقت و O(1) memory. والدرس الأكبر: فكرة من مسألة (المتوقع ناقص الموجود) بتتنقل لمسألة شكلها مختلف خالص. وده سبب إنك بتحل كتير: عشان تجمع أفكار.

دلوقتي تتمرن على الـ steps على مسائل حقيقية، بالترتيب.

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

مسائل سهلة، والهدف إنك تمشي على الـ 8 steps كاملة في كل واحدة، حتى لو الحل باين: comments، و dry-run على edge case قبل Submit. وعدّ: كام مرة أول Submit عدّى؟ ده المقياس الحقيقي.

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

الخلاصة

في جملة واحدة ما تكتبش كود قبل ما تفهم وتجرّب بإيدك، وما تدوسش Submit قبل dry-run على edge case. والحل السريع هو الـ brute force بعد ما تشيل منه الشغل اللي بيتكرر.
السؤالالإجابة
< ولا <=؟النهاية داخلة؟ <=. indices من 0؟ < n.
الـ loop بتلف كام مرة؟b - a مع <، و b - a + 1 مع <=.
r - l + 1 ولا r - l؟بتعدّ عناصر؟ + 1. مسافة؟ من غيرها. جرّب l = r.
القيمة الأولى؟أي عنصر حقيقي يكسبها: -Infinity للـ max، Infinity للـ min.
Wrong Answer؟dry-run على أصغر input، وبعدين الـ edge cases.
TLE؟الـ constraints، والـ complexity، و loop مستخبية.

الفصل الجاي: Big-O والـ Complexity. هنا قلنا كذا مرة "ده O(n²) يعني TLE" و "الـ includes loop مستخبية". الفصل الجاي بيشرح ده من الأول: إزاي تعدّ العمليات، وليه بنشيل الثوابت، وإزاي تحسب complexity لـ loops غريبة و recursion، وإيه في JS اللي شكله سطر وهو loop كاملة. ده اللي هيخليك تعمل step 3 و 4 و 8 بثقة.