إزاي تحل أي مسألةproblem-solving framework · understand → brute force → optimize → test
الفرق بين اللي بيحل واللي بيتلخبط مش الذكاء. الفرق إن الأول عنده steps ثابتة بيمشي عليها في كل مسألة، من أول ما يقرا لحد ما يدوس Submit. الفصل ده بيديك الـ steps دي، وبيقفل باب أشهر bug في الدنيا: الـ off-by-one.
هتطلع من الفصل ده وإنت عارف
- تمشي على 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 في أقل من دقيقة.
- افهم: قول المسألة بكلامك، اسأل، واقرا الـ constraints.
- أمثلة: مثال صغير بإيدك، وبعدين الـ edge cases.
- Brute force: أبسط حل صح، حتى لو بطيء، والـ complexity بتاعته.
- حسّن: دوّر على الـ bottleneck والشغل المتكرر، واختار data structure.
- خطة: الـ steps كـ comments قبل الكود.
- كود: املا تحت كل comment.
- اختبر: dry-run بـ trace table على مثال صغير و edge case.
- حلّل: الـ time والـ space complexity وليه.
طب إمتى بالظبط ترجع للـ checklist دي؟ وتعمل إيه لو حاجة باظت؟
إمتى تستخدم الـ steps دي
حتى لما تختصر، ما تختصرش step 7 (الـ dry-run). المسائل اللي إنت واثق منها هي بالظبط اللي بيعدّي فيها off-by-one.
| الـ step | بيطلع منها إيه | وقتها في انترفيو 45 دقيقة |
|---|---|---|
| 1. افهم | سطر input → output، و target complexity | 3 لـ 5 دقايق |
| 2. أمثلة | 3 لـ 5 أمثلة بإجاباتها | 2 لـ 3 دقايق |
| 3. Brute force | فكرة + complexity | 2 لـ 3 دقايق |
| 4. حسّن | فكرة أسرع + complexity | 5 لـ 10 دقايق |
| 5 و 6. خطة وكود | حل كامل | 12 لـ 17 دقيقة |
| 7. اختبر | bugs اتمسكت | 5 دقايق |
| 8. حلّل | جملتين | 1 دقيقة |
| اللي حصل | ارجع لـ | ليه |
|---|---|---|
| Wrong Answer | step 7، وبعدين 2 | غالبًا edge case ما جرّبتهوش، أو off-by-one. |
| TLE | step 1، وبعدين 4 | الـ complexity أكبر من اللي الـ constraints تسمح بيه، أو فيه hidden cost (Big-O). |
| Runtime Error | step 2 | input فاضي، 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 .... لو مش عارف تكتبه، يبقى لسه ما فهمتش. ودوّر على التفاصيل اللي بتغيّر كل حاجة:
- الـ range: "من 1 لحد n" يعني n داخلة. ده اللي وقّعك في FizzBuzz.
- شكل الإجابة: index ولا value؟ 0-indexed ولا 1-indexed (زي Two Sum II)؟ array ولا string؟ return ولا print؟
- لو مفيش إجابة:
-1؟[]؟0؟ - in-place: مسموح تعدّل الـ input؟
ب) اسأل 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 لحد | المسموح تقريبًا | معناها |
|---|---|---|
| 20 | O(2ⁿ) | جرّب كل الاحتمالات، عادي. |
| 500 | O(n³) | تلات loops جوه بعض. |
| 5,000 | O(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 قبل ما تفكّر في الحل.
فهمت المطلوب. بس على أنهي input هتجرّب حلّك؟
Step 2: أمثلة بإيدك و edge cases
أمثلة المسألة دايمًا "happy path"، والـ judge عنده tests مستخبية عكسها بالظبط. فبتعمل حاجتين:
- مثال صغير تحله بإيدك: 4 لـ 6 عناصر، على ورقة، من غير كود. وراقب دماغك بيعمل إيه: بيدوّر على إيه؟ بيفتكر إيه؟ ده أول draft للـ algorithm.
- قائمة edge cases كـ comments، ترجعلها في step 7.
| الحالة | مثال | بتكسر إيه غالبًا |
|---|---|---|
| فاضي | [] "" n = 0 | nums[0] = undefined. |
| عنصر واحد | [5] | أي مقارنة بالجيران. |
| كله زي بعضه | [3, 3, 3] | < مقابل <=، والتكرار. |
| سالب وأصفار | [-3, 0, -1] | max = 0، والضرب في صفر. |
| مترتب / بالعكس | [1, 2, 3] [3, 2, 1] | الإجابة في أول أو آخر عنصر. |
| مفيش إجابة | target مش موجود | نسيت الـ return بعد الـ loop. |
| أكبر حجم | n = 10⁵ | TLE، والـ recursion العميقة. |
عندك أمثلة بإجاباتها. أول حل تكتبه يبقى إيه؟
Step 3: Brute force الأول
ناس كتير بتتكسف من الحل البطيء وبتدوّر على الذكي على طول. وده غلط لأن الـ brute force:
- صح أكيد: بيجرّب كل حاجة.
- نقطة البداية: الحل السريع غالبًا هو الـ brute force بعد ما تشيل منه الشغل المتكرر. من غيره مش هتعرف إيه اللي بيتكرر.
- بيطمّن الـ interviewer: حل بطيء صح أحسن من حل سريع غلط أو من السكوت.
- بيختبر الحل السريع: تشغّلهم الاتنين على inputs عشوائية وتقارن. ده اسمه stress test.
مثال: مسألة البورصة (هنحلها كاملة تحت). سعر سهم كل يوم، تشتري في يوم وتبيع في يوم بعده، وعايز أكبر مكسب. الـ brute force: لكل يوم بيع، جرّب كل أيام الشرا اللي قبله:
حوالي n²/2 زوج. مع n = 10⁵ يبقى 5 × 10⁹ عملية، حوالي 50 ثانية: TLE. بس دلوقتي معاك حاجة صح تبني عليها. ولما تكتب الحل السريع، الـ brute force بيراجعه:
ليه inputs صغيرة؟ عشان لو فيه bug، يظهرلك على 3 أرقام تقدر تعمل عليهم dry-run بإيدك.
الـ brute force بطيء. إزاي تلاقي الأسرع بنظام، مش بالحظ؟
Step 4: حسّن
مفيش سحر. فيه 3 أسئلة بتسألهم للـ brute force بالترتيب:
- فين الـ bottleneck؟ غالبًا الـ loop الداخلية: هي اللي بتحوّل O(n) لـ O(n²). ركّز عليها.
- فيه شغل بيتكرر؟ الـ loop الداخلية بتحسب حاجة، وفي اللفة الجاية بتحسبها تاني من الأول تقريبًا؟ احفظها في متغير وحدّثها. في البورصة: الـ loop الداخلية بتدوّر على أقل سعر قبل يوم البيع، ولما يوم البيع يتحرك خطوة، الـ min ده بيتغيّر بعنصر واحد بس.
- السؤال اللي بيتكرر كل لفة إيه؟ لو سؤال بسيط، غالبًا فيه data structure بتجاوبه في O(1) أو O(log n).
| السؤال اللي بيتكرر | الأداة | الفصل |
|---|---|---|
| "الرقم ده شفته قبل كده؟" | Set | Hash Map و Set |
| "شفته كام مرة؟ أو فين؟" | Map | Hash Map و Set |
| "أصغر أو أكبر حاجة so far؟" | متغير واحد | مثال 3 تحت |
| "مجموع العناصر من l لـ r؟" | prefix sum | Prefix Sum |
| "فيه زوج مجموعه X في array مترتبة؟" | two pointers | Two Pointers |
| "أطول جزء متصل بشرط؟" | sliding window | Sliding Window |
| "أول مكان الشرط بيبقى فيه true؟" | binary search | Binary Search |
| "آخر حاجة اتفتحت وما اتقفلتش؟" | stack | Stack |
| "أصغر حاجة من مجموعة بتتغير؟" | heap | Heap |
وسؤال رابع بيوفّر وقت: إيه أحسن حل ممكن أصلًا؟ لو لازم تقرا كل عنصر عشان تجاوب، مفيش أسرع من O(n). فلو وصلت O(n)، ما تضيّعش وقت تدوّر على أحسن.
لقيت الفكرة. قبل ما تكتب: إزاي ترتّبها عشان الكود يطلع صح من أول مرة؟
Step 5 و 6: الخطة كـ comments، وبعدين الكود
وإنت بتكتب كود، دماغك شايل حاجتين: الـ algorithm والـ syntax. والـ comments بتخلّيك تخلص من الأول قبل التاني. وفي الانترفيو الـ interviewer بيشوف الخطة ويقولك لو فيها مشكلة قبل 10 دقايق كود. ده القالب اللي تفتح بيه أي مسألة:
- سطر input → output. لو مش عارف تكتبه، ارجع اقرا تاني. ده أرخص وقت تكتشف فيه إنك فاهم غلط.
- الأسئلة وإجاباتها. لما تيجي تكتب، هتفتكر إن فيه سالب فمش هتكتب
max = 0. - الـ target complexity. بيمنعك تضيّع وقت في حل عارف إنه هياخد TLE.
- الأمثلة بالإجابات المتوقعة. من غيرها الـ dry-run ملوش لازمة، لأنك مش هتعرف تقارن بإيه.
- الـ brute force والفكرة الأحسن، كل واحد في سطر. لو الفكرة مش بتتقال في جملة، لسه مش واضحة.
- الـ state: شايل إيه معاك وإنت ماشي، وقيمته الأولى إيه. نص الـ bugs بتيجي من القيمة الأولى:
0ولا-Infinityولاnums[0]. - إيه اللي بيحصل لكل عنصر. لو الإجابة فيها "وارجع لكل اللي فات"، ده O(n²) مستخبي.
- إيه اللي بيترجع. ساعات المتغير نفسه، وساعات حاجة محسوبة منه.
- الـ 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:
- هنا الـ bug.
max = 0معناها إنك افترضت إن فيه رقم ≥ 0، والمسألة ما قالتش كده. لو كله سالب، الـ function هترجّع 0، وده مش موجود في الـ array أصلًا. - loop على كل index من 0 لـ
length - 1. الـ<صح هنا. - لو الرقم الحالي أكبر من أكبر رقم so far، يبقى هو الأكبر الجديد.
- وعلى array فاضية بترجّع 0، وده كمان محتاج قرار: المسألة عايزة إيه هنا؟
المثال العادي مش هيكشفها. dry-run على edge case من الجدول: كله سالب.
الـ trace table بيّنت المشكلة في 3 rows: max عمره ما اتغيّر. الـ fix: قيمة أولى أي رقم حقيقي يكسبها:
- أصغر مثال عادي الأول (3 لـ 5 عناصر). على 20 عنصر هتزهق وتبدأ "تتخيّل" بدل ما تحسب.
- بعدين edge case مرتبط بالكود: فيه
max؟ جرّب سالب. فيهnums[i + 1]؟ جرّب عنصر واحد. - احسب من الكود مش من دماغك. لو السطر
i < n، اكتبه بالأرقام:5 < 5؟ لأ. يبقى الـ loop وقفت.
الكود صح. فاضل تقول هو سريع قد إيه.
Step 8: قول الـ complexity وليه
إنت حسبتها في step 3 و 4، دلوقتي بتأكّدها على الكود الفعلي:
- Time: عدّ الـ loops. loop على n يبقى O(n). nested يبقى O(n²).
sortيبقى O(n log n). وخلي بالك من methods شكلها سطر وجواها loop:includes،indexOf،shift. - Space: الـ memory الزيادة: array بطول n يبقى O(n).
Setفيه n عنصر يبقى O(n). شوية متغيرات يبقى O(1).
وقولها مع السبب: "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 المطلوب.
ب) عدد العناصر ولا المسافة؟
| السؤال | المعادلة | l = 3، r = 7 | بيظهر فين |
|---|---|---|---|
| عدد العناصر في [l, r] | r - l + 1 | 5 | طول window في sliding window |
| المسافة من l لـ r | r - l | 4 | العرض في Container With Most Water |
| عدد العناصر في [l, r) | r - l | 4 | slice(l, r) |
| عدد العناصر بين l و r | r - l - 1 | 3 | Trapping 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
- بتبدأ منين؟ 0؟ 1؟
i + 1؟ - النهاية داخلة؟ ده اللي بيقرر
<ولا<=. - بتلف كام مرة؟ بالقاعدة، وقارن باللي المسألة عايزاه.
وبعدين جرّب في دماغك n = 1 و n = 0. ده الملخص في كود واحد:
- الأشهر: من 0 لأن أول index صفر، و
<لأن آخر indexn - 1. بتلف n مرة. - لما المسألة بتتكلم عن أرقام مش indices: البداية 1 والنهاية داخلة، فـ
<=. - من
n - 1(مشn)، و>= 0عشان index صفر يتعالج.> 0هتفوّت أول عنصر. - من 1 لأن أول عنصر مالوش حد قبله. ولو بتقارن بـ
nums[i + 1]بدلnums[i - 1]، الشرط يبقىi < n - 1. - الـ +1 عشان العنصر اللي عند
lنفسه بيتحسب. المسافة بتعدّ الخطوات مش النقط. - من
lلـr - 1. لو عايز لحدrشامل:slice(l, r + 1).
كده معاك الـ steps والـ bug الأشهر. فاضل اللي الانترفيو بيركّز عليه: بتقول إيه وإنت بتحل؟
إزاي تتكلم وإنت بتحل
الـ interviewer بيقيّم طريقة تفكيرك، وما يقدرش يشوفها إلا لو قلتها. 5 دقايق سكوت وبعدين كود كامل بتقلقه أكتر من حل بطيء متشرح كويس.
| الـ 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 هي أهم جملة: بتسمّي الشغل المتكرر بالاسم. ولو وقفت:
- قول إنت فين: "I have O(n²), I think the inner loop can go, but I'm not sure with what yet."
- ارجع للمثال وحله بصوت عالي. الفكرة غالبًا بتطلع وإنت بتحل.
- اطلب hint بشكل محترم: "Am I going in the right direction?" الـ hint بيخصم أقل بكتير من السكوت.
- ما تعملش إنك متأكد وإنت مش متأكد: "I think it's O(n log n) because of the sort, let me double check."
نطبّق الـ steps كلها على 3 مسائل. كل واحدة بتضيف فكرة جديدة على اللي قبلها.
مثال محلول 1: FizzBuzz
رجّع array فيها n string. العنصر رقم i (لكل i من 1 لـ n) يبقى "FizzBuzz" لو i بيقبل القسمة على 3 و 5، و "Fizz" لو على 3 بس، و "Buzz" لو على 5 بس، وغير كده الرقم كـ string.
هنا مفيش optimization. الفكرة كلها في step 1 و 2: الـ range وترتيب الشروط.
- افهم:
in: n → out: n strings. "من 1 لحد n" يعني [1, n]، n عنصر بالظبط. والإجابة strings:"7"مش7. الـ constraintn <= 10⁴، فـ O(n) تمام. - أمثلة:
n = 1(لازم عنصر واحد)،n = 5، وn = 15اللي بيختبر ترتيب الشروط. - Brute force = الحل: loop وكام
if. O(n)، ومفيش أسرع لأن الإجابة نفسها n عنصر. - الخطة: loop من 1 لـ n شامل، الشرط الأخص الأول (15)، بعدين 3، بعدين 5، بعدين الرقم.
constلأن الاسم مش هيشاور على array تانية. الـpushبيعدّل جواها، وده مسموح.- أهم سطر. البداية 1 لأن العدّ من 1، و
<=لأن n داخلة. عدد اللفّاتn - 1 + 1 = n. جرّبn = 1:1 <= 1، فبتلف مرة. تمام. - ليه 15 الأول؟ أي مضاعف لـ 15 مضاعف لـ 3 كمان. لو شرط الـ 3 الأول، الـ 15 هيدخل فيه ويطلع
"Fizz". القاعدة فيif / else if: الأخص الأول. - لو وصلنا هنا يبقى مش مضاعف لـ 15. فلو على 3، يبقى على 3 بس، ونفس الكلام لـ 5.
String(i)لأن الإجابة strings.push(i)هيحط رقم، والـ judge هيقارن"7"بـ7: Wrong Answer.- الـ 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 ما فيهاش step 4. المسألة الجاية فيها brute force بطيء لازم يتحسّن.
مثال محلول 2: Missing Number
array فيها n رقم مختلفين، كلهم من [0, n]. الـ range ده فيه n + 1 رقم، فواحد ناقص. رجّعه.
الجديد هنا: step 4 كاملة. الـ brute force O(n²)، وهنحسّنه مرتين: مرة بـ data structure، ومرة بفكرة بتشيل الـ memory الزيادة.
- افهم: أول trap في الـ range:
[0, n]فيهn + 1رقم. لو الطول 2، الممكن 0 و 1 و 2، فـ[0, 1]إجابتها 2. - أمثلة: الناقص في النص (
[3, 0, 1])، هو n ([0, 1])، هو الصفر ([1]→ 0). - Brute force: لكل رقم من 0 لـ n،
includes. والـincludesloop مستخبية، فدهO(n²). - تحسين 1، السؤال المتكرر: "الرقم ده موجود؟" ده سؤال
Set. O(n) وقت بس O(n) memory. (أو sort وأولnums[i] !== i: O(n log n).) - تحسين 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.
- طول الـ array هو نفسه أكبر رقم في الـ range: n رقم من n + 1 احتمال.
- مجموع 1..n هو
n(n + 1)/2، والصفر مش بيزوّد. ليه n مش n - 1؟ لأن الـ range بيوصل لـ n شامل. والقسمة على 2 دايمًا صحيحة، لأن واحد منnوn + 1زوجي. for...ofلأننا مش محتاجين index، فأقل فرصة لـ off-by-one.- الفرق = الرقم اللي ما اتجمعش.
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، وده أحسن ممكن لأن لازم تشوف كل رقم.
هنا التحسين جه من فكرة رياضية. في المسألة الجاية بييجي من حاجة أعم: شيل الشغل اللي بيتكرر.
مثال محلول 3: Best Time to Buy and Sell Stock
prices[i] سعر سهم في اليوم i. عملية واحدة: تشتري في يوم، وتبيع في يوم بعده. رجّع أكبر مكسب، أو 0 لو مفيش مكسب.
الجديد هنا: الـ optimization بيشيل loop كاملة عن طريق state بيتحدّث وإحنا ماشيين (running min). ده pattern هتشوفه في نص المسائل الجاية.
- افهم:
max(prices[sell] - prices[buy])بشرطbuy < sell. و"رجّع 0" يعني إن مش تشتري خالص مسموح. الـ constraintn <= 10⁵: O(n²) = TLE. - أمثلة: أسعار نازلة (0)، يوم واحد (0)، و
[2, 4, 1]اللي بيكسر فكرة "أكبر سعر ناقص أصغر سعر":4 - 1 = 3، بس الـ 1 جه بعد الـ 4. الإجابة 2. - Brute force: كود step 3 فوق:
O(n²). - الـ key insight: لما يوم البيع ثابت، أحسن شرا هو أرخص يوم قبله. فالـ loop الداخلية كلها بتحسب
min(prices[0..sell - 1])، ولماsellيزيد، الـ min بيتغيّر بعنصر واحد. نشيله فيminPriceونحدّثه، والـ loop الداخلية تختفي.
- ليه
Infinityمش 0؟ مع 0، مفيش سعر أقل منه، فالمكسب هيتحسب كأنك اشتريت ببلاش. نفس bug الـfindMaxبالعكس.prices[0]صح برضه لو الـ array مش فاضية. - 0 مش
-Infinity، لأن "ما اشترتش" مسموح ومكسبه صفر. مع-Infinityوالأسعار نازلة هترجّع سالب. - أرخص سعر شامل النهارده. لو النهارده هو الأرخص، السطر الجاي هيحسب
price - price = 0، كأنك اشتريت وبعت في نفس اليوم، وده مش بيضر. ولو بدّلت السطرين، الحل برضه صح. - لو بعت النهارده، أحسن شرا هو
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.
[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 تلقائي.
تمرين: فكّر قبل ما تفتح
t اتعمل من s بإنك لخبطت حروفه وزوّدت حرف واحد في أي مكان. رجّع الحرف الزيادة. امشي على الـ steps.
تلميح 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 عدّى؟ ده المقياس الحقيقي.
- Fizz Buzzالمثال المحلول. قول بصوت عالي ليه
<=وليه 15 الأول. - Richest Customer Wealthnested loop على 2D. الحدود:
accounts.lengthولاaccounts[i].length؟ - Sign of the Product of an Arrayالـ edge case هو المسألة: صفر. وما تضربش فعلًا، عدّ السوالب.
- Max Consecutive Onesstate بسيط: عدّاد حالي وأحسن عدّاد. dry-run على array آخرها 1.
- Kids With the Greatest Number of Candiespass يجيب الـ max، و pass يجاوب. O(n) مش O(n²).
- How Many Numbers Are Smaller Than the Current Number
n <= 500: الـ brute force مقبول. بعدين حسّنه بالعدّ، القيم لحد 100. - Missing Numberالمثال المحلول. اكتب الـ Set والـ sort والمجموع وقارن.
- Find the Differenceالتمرين: نفس فكرة المجموع على حروف.
- Best Time to Buy and Sell Stockالمثال المحلول 3. اكتب الاتنين واعمل stress test.
- Maximum Difference Between Increasing Elementsنفس الـ running min، بس لو مفيش فرق موجب الإجابة
-1مش 0. اقرا الفرق كويس.
خلّصتهم؟ الفصل كله في صفحة واحدة تحت.
الخلاصة
| السؤال | الإجابة |
|---|---|
< ولا <=؟ | النهاية داخلة؟ <=. 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 بثقة.