Two Pointerstwo pointers · opposite ends · read / write · fast & slow

بدل ما تجرّب كل الأزواج بـ loop جوه loop، بتحط اتنين pointers وتحرّكهم بذكاء. كل حركة بتشيل احتمالات كتير مرة واحدة، فالـ O(n²) بيبقى O(n).

قبله: Arrays و Strings و Big-O بيمهّد لـ: Sliding Window و Linked List

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

  • تعرف من كلام المسألة إنها two pointers، وأنهي نوع من التلاتة.
  • تفهم ليه تحريك الـ pointer صح ومش بيضيّع إجابة، مش بس تحفظ القالب.
  • تكتب القوالب التلاتة من دماغك، وتعرف ليه كل سطر مكتوب كده: < ولا <=، و length - 1، و write - 1.
  • تحل Valid Palindrome و Container With Most Water و 3Sum، وتعرف تشرحهم في انترفيو.

ليه Two Pointers؟

في الفصل اللي فات استخدمنا hash map عشان نفتكر اللي شفناه. هنا هنستغل معلومة تانية خالص: إن الـ array مترتبة.

خد المسألة دي: array مترتبة من الأصغر للأكبر، وعايز رقمين مجموعهم يساوي target. أول حل بييجي في دماغ أي حد: جرّب كل pair.

الحل ده صح، بس بطيء. لو الـ array فيها n عنصر، عدد الأزواج حوالي n²/2. يعني لو n = 100,000، هيعمل حوالي 5 مليار مقارنة. السيرفر بيعمل حوالي 100 مليون عملية في الثانية، يعني هتاخد حوالي 50 ثانية، والاختبار بيديك ثانية أو اتنين. النتيجة: Time Limit Exceeded.

بص على الحل البديهي وهو شغال على 8 أرقام بس. عدّ معاه كام مقارنة عمل لحد ما لقى الإجابة:

17 مقارنة على 8 أرقام بس. والأسوأ إنه ما استفادش خالص من إن الـ array مترتبة. الترتيب ده معلومة ببلاش، والحل التاني هيستغلها.

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

ده بالظبط الحل بـ two pointers. نفس الـ array ونفس الـ target:

4 مقارنات بدل 17. وعلى n = 100,000 هيعمل 100,000 مقارنة بالكتير بدل 5 مليار. ده الفرق بين O(n²) و O(n).

طب إزاي تعرف من كلام المسألة إنها two pointers أصلًا؟ ده الجزء الجاي.

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

Two pointers مش pattern واحد، دول تلات أنواع بيشتركوا في فكرة واحدة: بدل index واحد بيلف، عندك اتنين بيتحركوا بقواعد. الكلمات دي في المسألة بتقولك إنه غالبًا two pointers:

لما تشوف: sorted arraypair / triplet with sumpalindromereverse in-placeO(1) extra spaceremove duplicatesmove zeroes merge two sortedmiddle of linked listcycle
ومش هو غالبًا لو: unsorted + return indicescount subarrays with sum k (negatives)longest substring with condition

آخر سطر ده مهم. لو الـ array مش مترتبة ومطلوب ترجع الـ indices الأصلية، مش هينفع ترتّبها لأن الترتيب هيضيّع الـ indices، فالحل هيبقى hash map. ولو المطلوب "أطول جزء متصل"، ده sliding window، وهو في الحقيقة two pointers بيمشوا في نفس الاتجاه، وهتشوفه في الفصل الجاي.

النوعالـ pointers بيبدأوا فينبيتحركوا إزايأشهر مسائل
من الطرفين
opposite ends
left = 0، right = n - 1بيقرّبوا من بعض لحد ما يتقابلواTwo Sum II، Valid Palindrome، Container With Most Water، 3Sum
نفس الاتجاه
read / write
الاتنين من الأولread بيمشي كل خطوة، write بيمشي بشرطRemove Duplicates، Move Zeroes، Remove Element
سريع وبطيء
fast & slow
الاتنين من الأولfast خطوتين، slow خطوةMiddle of Linked List، Linked List Cycle
flowchart TD
  A["Two pointers?"] --> B{"Sorted array, pair, or palindrome?"}
  B -- yes --> O["Opposite ends: left = 0, right = n - 1"]
  B -- no --> C{"Edit the array in place / keep a clean prefix?"}
  C -- yes --> S["Same direction: read + write"]
  C -- no --> D{"Linked list: middle or cycle?"}
  D -- yes --> F["Fast and slow"]
  D -- no --> H["Probably another pattern: hash map or sliding window"]
  

اسأل نفسك الأسئلة دي بالترتيب ده.

يلا نبدأ بأشهر نوع فيهم، اللي شفناه فوق: من الطرفين، ونفهم كل سطر في الـ template بتاعه.

النوع الأول: من الطرفين

نرجع لمسألة الرقمين. القالب كله 14 سطر، بس كل سطر فيهم ليه سبب. امشي على الشرح واحدة واحدة، أو دوس على أي سطر رقمه ملوّن:

  1. الدالة بتاخد array مترتبة تصاعدي و target. لو المسألة ما قالتش إنها مترتبة، يبقى القالب ده مش هينفع إلا لو رتّبتها الأول، وده بيبوّظ الـ indices الأصلية.
  2. الـ left بيبدأ عند أصغر رقم في الـ array.
  3. الـ right بيبدأ عند آخر index وهو nums.length - 1، مش nums.length. الـ indices بتبدأ من 0، فلو الطول 8 يبقى آخر index هو 7. لو كتبت nums.length، nums[8] هتطلع undefined، والمجموع هيبقى NaN. والـ NaN مش أكبر ولا أصغر من أي رقم، فكل المقارنات هتطلع false من غير أي error، وده bug صعب تلاقيه.
  4. ليه < مش <=؟ لأن لما left === right الاتنين بيشاوروا على نفس العنصر. لو كتبت <= هتجمع العنصر مع نفسه. مثلًا [1, 4, 9] و target = 8: لما الاتنين يقفوا على الـ 4، 4 + 4 = 8، فهترجّع [1, 1]، وده غلط لأن المسألة عايزة رقمين مختلفين. ولما يتقابلوا، يبقى ما فضلش أي زوج ما اتجرّبش، فالـ loop خلصت.
  5. بنجمع الرقمين اللي عند الـ pointers. مفيش loop جوه loop، كل لفة فيها مقارنة واحدة بس.
  6. لقينا الإجابة، فبنرجّع على طول. === مش ==، عشان في JS الـ == بيحوّل الأنواع: "8" == 8 بتطلع true.
  7. ليه نحرّك left لما المجموع أصغر؟ لأن nums[left] مع أكبر رقم موجود (nums[right]) لسه ما وصلش للهدف. فـ nums[left] مع أي رقم تاني أصغر أكيد مش هيوصل. يعني nums[left] مالوش أي زوج ينفع، فبنشيله من الحسبة بأمان. ده سبب إن الحل صح، مش مجرد إحساس.
  8. نفس المنطق بالعكس: nums[right] مع أصغر رقم متاح (nums[left]) طلع أكبر من الهدف. فمع أي رقم تاني أكبر هيطلع أكبر برضه. يبقى nums[right] مالوش زوج، فبنشيله.
  9. لو الـ pointers اتقابلوا ولقيناش حاجة، يبقى مفيش زوج. [-1, -1] هو المتعارف عليه، بس اقرا المسألة: ساعات بتطلب [] أو null.

شوفه وهو بيتحرك، سطر بسطر

الـ animation تحت مربوطة بالكود: السطر اللي بيتنفّذ بيتلوّن، والمتغيرات بتظهر تحت الشرح. الخانات اللي اتشالت من الحسبة بتبهت.

الفكرة اللي لازم تفضل معاك كل حركة pointer هي إثبات إن العنصر اللي سبناه مالوش إجابة. عشان كده بنشيل عنصر كامل مع كل مقارناته في خطوة واحدة. ده اللي بيخلّي الـ O(n²) يبقى O(n).

في الـ animation، عند الخطوة اللي فيها 3 + 15 = 18 وده أكبر من 17. ليه شلنا الـ 15 ومش الـ 3؟

  • عشان الـ 3 صغيرة
  • عشان 15 مع أصغر رقم متاح (3) طلع أكبر من الهدف، فمع أي رقم أكبر هيطلع أكبر برضه
  • عشان دايمًا بنحرّك الـ right الأول
  • مش فارقة، ممكن نشيل أي واحد فيهم

الـ 3 لسه ممكن ليها زوج (مع 13 أو 14 مثلًا)، فلو شلناها ممكن نضيّع الإجابة. لكن الـ 15 مالهاش زوج أكيد. وفعلًا الإجابة طلعت 4 + 13.

طب لو المطلوب مش pair خالص، المطلوب تنضّف الـ array نفسها in-place؟ هنا الاتنين pointers بيمشوا في نفس الاتجاه.

النوع التاني: نفس الاتجاه (read و write)

المسألة: عندك array مترتبة فيها أرقام متكررة. شيل التكرار in-place، يعني من غير array جديدة، ورجّع عدد الأرقام المختلفة. LeetCode 26.

الفكرة إن الـ array بتتقسم لجزئين:

الـ read بيمشي على كل عنصر. لو لقى رقم جديد مش موجود في آخر الجزء النضيف، بيكتبه عند write، والـ write يتحرك خطوة.

تشبيه واحد بيقرا أسامي من كشف مترتب (ده read)، وواحد تاني بينقل في كشف نضيف (ده write). الناقل بيكتب الاسم بس لو مختلف عن آخر اسم كتبه. القارئ عمره ما بيقف، والناقل بيتحرك ساعات بس.
  1. حالة طرفية: array فاضية. من غير السطر ده، الدالة هترجّع 1 والإجابة الصح 0. دايمًا فكّر في الـ input الفاضي.
  2. ليه write بيبدأ من 1 مش 0؟ لأن أول عنصر عمره ما بيبقى مكرر، ما فيش حاجة قبله. فهو من الأول جزء من الجزء النضيف. الـ write معناه "المكان اللي هكتب فيه الرقم الجديد الجاي"، وكمان "طول الجزء النضيف لحد دلوقتي".
  3. الـ read بيبدأ من 1 لنفس السبب، العنصر 0 اتحسب خلاص. وبيمشي على كل عنصر مرة واحدة، فالـ loop دي O(n).
  4. ليه بنقارن بـ nums[write - 1] مش بـ nums[read - 1]؟ الـ nums[write - 1] هو آخر رقم في الجزء النضيف، يعني آخر رقم احتفظنا بيه. في المسألة دي بالذات الاتنين بيدّوا نفس النتيجة، لأن الـ array مترتبة. بس المقارنة بـ write - 1 هي الفكرة الصح والأعمّ. لو المسألة اتغيّرت لـ "خلّي كل رقم يتكرر مرتين بالكتير" (LeetCode 80)، الحل هيبقى nums[read] !== nums[write - 2]، وده مش هيشتغل مع read.
  5. بنكتب الرقم الجديد عند write. ساعات write === read فبيكتب الرقم مكانه، وده مش مشكلة.
  6. الجزء النضيف كبر بعنصر، فالمكان الجاي للكتابة اتحرك.
  7. بنرجّع write لأنه طول الجزء النضيف. اللي بعد write في الـ array مش مهم، والـ judge مش بيبص عليه.
نفس القالب في مسائل تانية Move Zeroes: بتكتب كل رقم مش صفر عند write، وبعد الـ loop تملا الباقي أصفار. Remove Element: بتكتب كل رقم مش بيساوي val. الشرط بس هو اللي بيتغيّر، والهيكل واحد.

فاضل نوع تالت: الاتنين بيمشوا في نفس الاتجاه، بس بسرعات مختلفة.

النوع التالت: سريع وبطيء

الاتنين بيبدأوا من نفس المكان، بس fast بيمشي خطوتين و slow خطوة واحدة. النوع ده مستخدم أكتر مع الـ linked list، وهنفصّله هناك، بس خد الفكرة من دلوقتي:

flowchart LR
  n1((1)) --> n2((2)) --> n3((3)) --> n4((4)) --> n5((5)) --> n6((6))
  n6 --> n3
  

List فيها دايرة: الـ 6 بترجع للـ 3. الـ fast هيفضل يلف جوه الدايرة لحد ما يقابل الـ slow.

ليه الشرط fast !== null && fast.next !== null؟ لأن fast هياخد خطوتين: fast.next.next. لو fast نفسه null هيطلع error لما تقرا .next. ولو fast.next هو اللي null، هيطلع error لما تقرا .next منه. فلازم الاتنين يكونوا موجودين.

كده عرفنا التلات أنواع. يلا نطبّقهم على مسائل حقيقية، ونبدأ بأسهلها: palindrome.

مثال محلول 1: Valid Palindrome

Valid Palindrome

easyLeetCode 125

عندك string. شيل منه أي حاجة مش حرف أو رقم، وتجاهل الفرق بين الحروف الكبيرة والصغيرة. هل يتقري زي ما هو من الناحيتين؟

Input: "No 'x' in Nixon" → true (noxinnixon) Input: "race a car" → false (raceacar) Input: " " → true (empty after cleaning)

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

  1. افهم المطلوب: مش هنقارن الـ string زي ما هو. هنتجاهل المسافات والعلامات، والـ N زي الـ n.
  2. أول حل بييجي في دماغك: نعمل string نضيف (حروف وأرقام بس، lowercase)، ونقارنه بمقلوبه. ده O(n) في الوقت، بس بيعمل نسختين جداد، يعني O(n) memory. حل كويس، وقوله في الانترفيو كبداية.
  3. نقدر نوفّر الـ memory؟ الـ palindrome معناه إن أول حرف زي آخر حرف، والتاني زي اللي قبل الآخر، وهكذا. يعني مقارنة من الطرفين، two pointers من غير ما نعمل أي string جديد: O(1) memory.
  4. المشكلة الوحيدة: العلامات. لما pointer يقف على علامة أو مسافة، نفوّتها لحد ما يقف على حرف أو رقم.
  5. الحالات الطرفية: string فاضي أو كله علامات (الإجابة true)، حرف واحد (true)، وحروف كبيرة وصغيرة مع بعض.
  1. نفس بداية القالب: واحد من الأول وواحد من الآخر.
  2. الـ < هنا مش بس عشان ما نقارنش الحرف بنفسه. لما يتقابلوا يبقى خلاص قارنّا كل الأزواج. وفي string طوله فردي، الحرف اللي في النص مالوش حد يتقارن بيه، وأي حرف لوحده palindrome أصلًا.
  3. ليه left < right مكررة جوه الـ while الداخلية؟ لو الـ string كله علامات زي "!!!"، الـ left هيفضل يزيد ويعدّي right ويخرج برا الـ string، و s[left] هتبقى undefined، وبعدها .toLowerCase() على undefined هيضرب error. الشرط ده بيوقفه في الوقت الصح.
  4. نفس الكلام من الناحية التانية.
  5. بنحوّل الاتنين لـ lowercase قبل المقارنة، عشان 'N' و 'n' يتحسبوا نفس الحرف. ولو مختلفين يبقى مش palindrome، ونرجّع false على طول من غير ما نكمّل.
  6. الزوج ده تمام، فبنقرّب الاتنين خطوة. لازم الاتنين يتحرّكوا. لو نسيت واحد، هتقارن نفس الحرف بحرف جديد والنتيجة هتبقى غلط.
  7. لو الـ loop خلصت من غير ما نلاقي اختلاف، يبقى palindrome.
  8. /[a-z0-9]/i regex معناها: حرف من a لـ z أو رقم، والـ i معناها تجاهل الكبير والصغير. ممكن بدلها تقارن بالـ char codes، بس دي أوضح وأسرع في الكتابة وقت الاختبار.

شوف الحل وهو شغال على "No 'x' in Nixon". المسافات بتظهر ␣:

Inputالمتوقعليه الحالة دي مهمة
""trueالـ right = -1، والـ while مش هتدخل أصلًا
"!!!"trueمن غير left < right في الـ while الداخلية، هيطلع برا الـ string
"a"trueحرف واحد بس
"0P"falseرقم وحرف: لازم الأرقام تتحسب حروف عادية
"Aa"trueالكبير والصغير

التعقيد: كل حرف بيعدّي عليه pointer واحد مرة واحدة، فالوقت O(n)، والـ memory O(1).

هنا كنا بنحرّك الاتنين مع بعض دايمًا. في المثال الجاي الجديد إننا لازم نختار نحرّك مين، ونثبت إن اختيارنا صح.

مثال محلول 2: Container With Most Water

Container With Most Water

mediumLeetCode 11

عندك حيطان طولها height[i]، وكل حيطة واقفة عند index i. اختار حيطتين يحبسوا أكبر كمية مية. المية مستواها بيبقى قد الحيطة الأقصر، وعرضها هو المسافة بين الحيطتين.

Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7] Output: 49 (walls at index 1 and 8: min(8, 7) * (8 - 1) = 7 * 7)

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

  1. المساحة = min(height[i], height[j]) × (j - i). الحيطة الأقصر هي اللي بتحدد الارتفاع.
  2. Brute force: جرّب كل زوج، O(n²). ومع n لحد 10⁵ هياخد TLE.
  3. نبدأ بأعرض حاجة: left = 0 و right = n - 1. ده أكبر عرض ممكن. بعد كده كل حركة هتقلّل العرض 1، فالمكسب الوحيد الممكن إن الارتفاع يزيد.
  4. نحرّك مين؟ دي أهم نقطة. لو حرّكت الحيطة الأطول، الارتفاع عمره ما هيزيد، لأن الأقصر لسه موجودة وهي اللي بتحدّد. والعرض قلّ. يعني المساحة هتقل أو تفضل زي ما هي. لكن لو حرّكت الأقصر، ممكن نلاقي حيطة أطول ترفع المستوى.
  5. الإثبات: الحيطة الأقصر، مع أي حيطة تانية جوه الرينج، مساحتها أقل من أو تساوي المساحة اللي حسبناها حالًا، لأن العرض أصغر والارتفاع مش هيعدّي طولها. فخلاص جرّبنا أحسن حاجة ليها، ونقدر نشيلها.
  1. نبدأ من أعرض container ممكن.
  2. best = 0 لأن أقل مساحة ممكنة صفر. ما بنحطش -Infinity لأن المساحة عمرها ما بتبقى سالبة.
  3. < عشان container محتاج حيطتين مختلفتين. حيطة لوحدها عرضها صفر.
  4. المستوى = الحيطة الأقصر. Math.min مش Math.max، لأن المية بتدلق من فوق الحيطة الأقصر.
  5. العرض = right - left، مش right - left + 1. إحنا بنقيس المسافة بين حيطتين، مش بنعدّ عناصر. الحيطة عند 1 والحيطة عند 8 المسافة بينهم 7. الـ +1 بيبقى لما بتعدّ عناصر subarray زي في الـ sliding window. فرّق بين الاتنين.
  6. بنحدّث أحسن مساحة شفناها.
  7. نحرّك الأقصر. ولو الاتنين متساويين بيدخل في الـ else ويحرّك right. ده صح، وكان ينفع نحرّك أي واحد، لأن لو الاتنين متساويين، أي حيطة جوه الرينج مع واحدة منهم مش هتدّي مساحة أكبر من اللي حسبناها. فالاتنين خلاص "استهلكوا" فرصتهم.

التعقيد: كل لفة بتحرّك pointer واحد خطوة، والاتنين بيتقابلوا بعد n - 1 خطوة بالكتير. يعني O(n) وقت و O(1) memory.

في الانترفيو الحل نفسه 8 سطور، والـ interviewer عارفه. اللي هيقيّمك عليه هو ليه نحرّك الأقصر. قول الإثبات اللي في الخطوة 5 بصوت عالي، حتى لو ما سألكش.

طب لو المطلوب 3 أرقام مش 2؟ هنرجّع المسألة لحاجة حليناها خلاص.

مثال محلول 3: 3Sum

3Sum

mediumLeetCode 15

طلّع كل الـ triplets المختلفة اللي مجموعها صفر. الـ triplet الواحدة ما تتكررش في الإجابة.

Input: nums = [-1, 0, 1, 2, -1, -4] Output: [[-1, -1, 2], [-1, 0, 1]]

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

  1. Brute force: تلات loops، O(n³). ومع n = 3000 (الـ constraint في LeetCode) ده 27 مليار عملية تقريبًا. مستحيل.
  2. نحوّلها لمسألة نعرفها: لو ثبّتنا الرقم الأول nums[i]، المطلوب يبقى رقمين مجموعهم -nums[i]. دي مسألة الـ pair sum اللي حليناها فوق، بس محتاجة array مترتبة.
  3. فنرتّب الأول: O(n log n). الترتيب هنا مش بيبوّظ حاجة، لأن المطلوب الأرقام نفسها مش الـ indices.
  4. لكل i نعمل two pointers على اللي بعده: left = i + 1 و right = n - 1. ده O(n) لكل i، فالمجموع O(n²). أحسن بكتير من O(n³).
  5. الصعب الحقيقي: التكرار. [-1, -1, 2] ما ينفعش تطلع مرتين. والحل في 3 أماكن: نفوّت i لو رقمها زي اللي قبلها، وبعد ما نلاقي triplet نفوّت الأرقام المكررة عند left وعند right.
  1. أخطر سطر في الحل. nums.sort() من غير comparator في JS بيرتّب الأرقام كأنها نصوص: [-1, -4, 10, 2].sort() بتطلع [-1, -4, 10, 2]، لأنها بتقارن الحروف "-" و "1". الـ (a, b) => a - b معناها: لو الناتج سالب يبقى a قبل b. ولو نسيته، الـ two pointers هتشتغل على array مش مترتبة فعلًا، والإجابات هتبقى غلط من غير أي error.
  2. ليه nums.length - 2؟ لأن i محتاج اتنين بعده (left و right). لو i وصل لآخر عنصرين، مش هيلاقي اتنين بعده. ممكن تكتب i < nums.length والحل هيشتغل، لأن الـ while الداخلية مش هتدخل، بس - 2 أوضح.
  3. ليه i > 0 الأول؟ لأن عند i = 0 مفيش nums[-1]، وهترجع undefined. الشرط ده بيحمي من كده. وليه نفوّت المكرر؟ لو nums[i] زي nums[i - 1]، يبقى كل الـ triplets اللي هتطلع من i طلعت قبل كده من i - 1. خلي بالك: بنقارن بالـ اللي قبله مش باللي بعده. لو قارنت بـ nums[i + 1] هتفوّت أول -1 وتضيّع [-1, -1, 2]، لأن الـ triplet دي محتاجة الاتنين -1.
  4. الـ two pointers بيبدأوا من بعد i، عشان ما نستخدمش نفس العنصر مرتين، وعشان الأزواج اللي قبل i اتجرّبت خلاص.
  5. مجموع التلاتة. لو مستنّي أرقام كبيرة جدًا، خلي بالك من الـ overflow في لغات تانية. في JS الأرقام لحد 2⁵³ مضمونة.
  6. لقينا triplet فبنسجّلها. وبنحط القيم مش الـ indices.
  7. بنحرّك الاتنين، لأن لو حرّكنا واحد بس، المجموع هيتغيّر ومش هيرجع صفر بنفس الـ pointer التاني، إلا لو الرقم مكرر، وده اللي السطرين الجايين بيفوّتوه.
  8. بنفوّت أي رقم زي اللي لسه سايبينه، عشان ما نطلّعش نفس الـ triplet تاني. والـ left < right عشان ما نعدّيش بعض.
  9. نفس الفكرة من اليمين. لاحظ إننا بنقارن بـ right + 1 لأن right اتحرك لورا، فاللي سبناه بقى على يمينه.
  10. نفس قرار الـ pair sum بالظبط: أصغر من الهدف يبقى نكبّر من الشمال، وأكبر يبقى نصغّر من اليمين.

التعقيد: الـ sort O(n log n)، والـ loop O(n) مرات two pointers O(n)، يعني O(n²) في المجموع. والـ memory O(1) غير الإجابة، أو O(log n) حسب الـ sort.

تحسين صغير بيعجب الـ interviewer لو nums[i] > 0، أقف خالص (break). كل اللي بعده أكبر منه لأن الـ array مترتبة، فمجموع تلات أرقام موجبة عمره ما هيبقى صفر.

شفت كام مكان ممكن يغلّطك فيه سطر واحد؟ يلا نجمع الغلطات دي في مكان واحد.

غلطات مشهورة

كل غلطة هنا شكلها صغير، بس بتطلّع Wrong Answer أو بتعلّق الكود. وكلهم بيحصلوا في الاختبارات فعلًا.

1. <= بدل <

الصح left < right. القاعدة: لو العنصرين لازم يكونوا مختلفين استخدم <. هتشوف <= في الـ binary search، وهناك ليها سبب تاني خالص.

2. نسيت تحرّك pointer: loop ما بتخلصش

أي فرع جوه الـ loop لازم يحرّك pointer واحد على الأقل. اسأل نفسك عن كل if: "هنا مين بيتحرك؟".

3. sort() من غير comparator

4. تستخدم two pointers على array مش مترتبة

الإثبات كله قايم على إن الشمال أصغر واليمين أكبر. على array مش مترتبة، تحريك left مش بيضمن إن المجموع يكبر، فالحل بيفوّت إجابات. يا ترتّب الأول (لو مش محتاج الـ indices)، يا تستخدم hash map.

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

nums.sort() بيرتّب الـ array الأصلية نفسها. لو المسألة بعد كده محتاجة الترتيب الأصلي، أو الـ caller بيستخدم نفس الـ array، اعمل نسخة الأول: const a = [...nums].sort((x, y) => x - y).

دلوقتي جرّب نفسك: كام سؤال سريع، وتمرين تفكّر فيه قبل ما تفتح الحل.

اختبر نفسك

array مش مترتبة، ومطلوب indices رقمين مجموعهم target. أحسن حل؟

  • نرتّب ونعمل two pointers
  • Hash map: لكل رقم نسأل "شفت target - x قبل كده؟"
  • Brute force بس
  • Fast & slow

الترتيب بيغيّر أماكن العناصر فبتضيع الـ indices الأصلية، إلا لو رتّبت أزواج [value, index]، وده O(n log n). الـ hash map بتحلها في O(n) ومن غير ترتيب، وده الفصل Hash Map.

في Container With Most Water، الحيطتين اللي عند الـ pointers طولهم واحد. نحرّك مين؟

  • الشمال بس، وإلا الحل يبقى غلط
  • اليمين بس، وإلا الحل يبقى غلط
  • أي واحد، الاتنين صح
  • الاتنين مع بعض لازم

لما الاتنين متساويين، أي container تاني فيه واحد منهم هيبقى عرضه أصغر وارتفاعه مش هيعدّي الطول ده. فالاتنين خلاص طلّعوا أحسن ما عندهم. تحريك أي واحد صح، وتحريك الاتنين صح برضه.

إيه الـ time complexity بتاعة 3Sum بالحل اللي فوق؟

  • O(n)
  • O(n log n)
  • O(n²)
  • O(n³)

الـ sort O(n log n)، وبعده loop على i فيها two pointers O(n)، يعني n × n. والـ n² أكبر من n log n، فهي اللي بتتحسب.

في Remove Duplicates، ليه write بيبدأ من 1؟

  • عشان الـ indices في JS بتبدأ من 1
  • عشان أول عنصر عمره ما بيبقى مكرر، فهو في الجزء النضيف من الأول
  • عشان نتجنب error
  • غلط، المفروض يبدأ من 0

write معناه "طول الجزء النضيف" و"المكان الجاي للكتابة". والجزء النضيف فيه من الأول عنصر واحد، وهو nums[0].

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

Squares of a Sorted Array

easyLeetCode 977

array مترتبة وفيها أرقام سالبة. رجّع مربعاتها مترتبة. هل تقدر في O(n) من غير sort؟

[-4, -1, 0, 3, 10] → [0, 1, 9, 16, 100]
تلميح 1

أكبر مربع فين؟ مش في النص أكيد. يا في أول الـ array (سالب كبير) يا في آخرها (موجب كبير).

تلميح 2

two pointers من الطرفين. قارن المربعين، والأكبر حطه في آخر الـ result وحرّك الـ pointer بتاعه. يعني بتملا الإجابة من الآخر للأول.

الحل

هنا left <= right ضمنيًا، لأن الـ loop بتلف n مرة بالظبط، وآخر عنصر بيتحط لما left === right. هنا مسموح الاتنين يقفوا على نفس العنصر، لأننا مش بنعمل زوج، بنحط كل عنصر مرة واحدة.

لو الأسئلة دي عدّت معاك، روح على LeetCode بالترتيب اللي تحت.

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

حلها بالترتيب ده، كل مسألة بتضيف فكرة واحدة جديدة. علّم على اللي خلّصته، والتقدّم بيتحفظ. لو قعدت أكتر من 25 دقيقة على مسألة، ارجع للقالب بتاعها هنا، وبعدين حاول تاني من غير ما تبص.

وآخر حاجة: الفصل كله في صفحة واحدة ترجعلها قبل أي انترفيو.

الخلاصة

في جملة واحدة Two pointers بيشتغل لما كل حركة pointer تقدر تثبت إن العناصر اللي سبتها مالهاش إجابة، أو إنها خلاص في مكانها الصح. ولو مش قادر تقول الإثبات ده، يبقى الـ pattern غالبًا مش ده.
السؤالالإجابة
< ولا <=؟< لو العنصرين لازم يكونوا مختلفين (زوج). <= لو كل عنصر لازم يتعالج لوحده (زي Squares).
right بيبدأ فين؟nums.length - 1، آخر index مش الطول.
نحرّك مين؟اللي تقدر تثبت إنه مالوش إجابة: الأصغر لو محتاج تكبّر، والأقصر في الـ container.
محتاج sort؟لو المطلوب قيم (3Sum) رتّب. ولو المطلوب indices أصلية استخدم hash map.
Complexity؟O(n) للطرفين و read/write. O(n log n) لو رتّبت. O(n²) لو فيه loop برا (3Sum).

الفصل الجاي: Sliding Window هو النوع التاني (نفس الاتجاه) بس بقاعدة مختلفة: الاتنين بيحدّدوا window متصلة، right بيكبّرها و left بيصغّرها لما تبقى غلط. كل اللي اتعلمته هنا عن "مين يتحرك وليه" هتستخدمه هناك على طول.