Two Pointerstwo pointers · opposite ends · read / write · fast & slow
بدل ما تجرّب كل الأزواج بـ loop جوه loop، بتحط اتنين pointers وتحرّكهم بذكاء. كل حركة بتشيل احتمالات كتير مرة واحدة، فالـ O(n²) بيبقى O(n).
هتطلع من الفصل ده وإنت عارف
- تعرف من كلام المسألة إنها 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 مترتبة. الترتيب ده معلومة ببلاش، والحل التاني هيستغلها.
ده بالظبط الحل بـ two pointers. نفس الـ array ونفس الـ target:
4 مقارنات بدل 17. وعلى n = 100,000 هيعمل 100,000 مقارنة بالكتير بدل 5 مليار. ده الفرق بين O(n²) و O(n).
طب إزاي تعرف من كلام المسألة إنها two pointers أصلًا؟ ده الجزء الجاي.
إزاي تعرفه من المسألة
Two pointers مش pattern واحد، دول تلات أنواع بيشتركوا في فكرة واحدة: بدل index واحد بيلف، عندك اتنين بيتحركوا بقواعد. الكلمات دي في المسألة بتقولك إنه غالبًا two pointers:
آخر سطر ده مهم. لو الـ 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 سطر، بس كل سطر فيهم ليه سبب. امشي على الشرح واحدة واحدة، أو دوس على أي سطر رقمه ملوّن:
- الدالة بتاخد array مترتبة تصاعدي و
target. لو المسألة ما قالتش إنها مترتبة، يبقى القالب ده مش هينفع إلا لو رتّبتها الأول، وده بيبوّظ الـ indices الأصلية. - الـ
leftبيبدأ عند أصغر رقم في الـ array. - الـ
rightبيبدأ عند آخر index وهوnums.length - 1، مشnums.length. الـ indices بتبدأ من 0، فلو الطول 8 يبقى آخر index هو 7. لو كتبتnums.length،nums[8]هتطلعundefined، والمجموع هيبقىNaN. والـNaNمش أكبر ولا أصغر من أي رقم، فكل المقارنات هتطلع false من غير أي error، وده bug صعب تلاقيه. - ليه
<مش<=؟ لأن لماleft === rightالاتنين بيشاوروا على نفس العنصر. لو كتبت<=هتجمع العنصر مع نفسه. مثلًا[1, 4, 9]و target = 8: لما الاتنين يقفوا على الـ 4،4 + 4 = 8، فهترجّع[1, 1]، وده غلط لأن المسألة عايزة رقمين مختلفين. ولما يتقابلوا، يبقى ما فضلش أي زوج ما اتجرّبش، فالـ loop خلصت. - بنجمع الرقمين اللي عند الـ pointers. مفيش loop جوه loop، كل لفة فيها مقارنة واحدة بس.
- لقينا الإجابة، فبنرجّع على طول.
===مش==، عشان في JS الـ==بيحوّل الأنواع:"8" == 8بتطلع true. - ليه نحرّك
leftلما المجموع أصغر؟ لأنnums[left]مع أكبر رقم موجود (nums[right]) لسه ما وصلش للهدف. فـnums[left]مع أي رقم تاني أصغر أكيد مش هيوصل. يعنيnums[left]مالوش أي زوج ينفع، فبنشيله من الحسبة بأمان. ده سبب إن الحل صح، مش مجرد إحساس. - نفس المنطق بالعكس:
nums[right]مع أصغر رقم متاح (nums[left]) طلع أكبر من الهدف. فمع أي رقم تاني أكبر هيطلع أكبر برضه. يبقىnums[right]مالوش زوج، فبنشيله. - لو الـ pointers اتقابلوا ولقيناش حاجة، يبقى مفيش زوج.
[-1, -1]هو المتعارف عليه، بس اقرا المسألة: ساعات بتطلب[]أوnull.
شوفه وهو بيتحرك، سطر بسطر
الـ animation تحت مربوطة بالكود: السطر اللي بيتنفّذ بيتلوّن، والمتغيرات بتظهر تحت الشرح. الخانات اللي اتشالت من الحسبة بتبهت.
في الـ 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 بتتقسم لجزئين:
- جزء نضيف من الأول لحد
write - 1: كل اللي فيه أرقام مختلفة ومترتبة. - جزء لسه ما اتقراش من
readلحد الآخر.
الـ read بيمشي على كل عنصر. لو لقى رقم جديد مش موجود في آخر الجزء النضيف، بيكتبه عند write، والـ write يتحرك خطوة.
read)، وواحد تاني بينقل في كشف نضيف (ده write). الناقل بيكتب الاسم بس لو مختلف عن آخر اسم كتبه. القارئ عمره ما بيقف، والناقل بيتحرك ساعات بس.
- حالة طرفية: array فاضية. من غير السطر ده، الدالة هترجّع 1 والإجابة الصح 0. دايمًا فكّر في الـ input الفاضي.
- ليه
writeبيبدأ من 1 مش 0؟ لأن أول عنصر عمره ما بيبقى مكرر، ما فيش حاجة قبله. فهو من الأول جزء من الجزء النضيف. الـwriteمعناه "المكان اللي هكتب فيه الرقم الجديد الجاي"، وكمان "طول الجزء النضيف لحد دلوقتي". - الـ
readبيبدأ من 1 لنفس السبب، العنصر 0 اتحسب خلاص. وبيمشي على كل عنصر مرة واحدة، فالـ loop دي O(n). - ليه بنقارن بـ
nums[write - 1]مش بـnums[read - 1]؟ الـnums[write - 1]هو آخر رقم في الجزء النضيف، يعني آخر رقم احتفظنا بيه. في المسألة دي بالذات الاتنين بيدّوا نفس النتيجة، لأن الـ array مترتبة. بس المقارنة بـwrite - 1هي الفكرة الصح والأعمّ. لو المسألة اتغيّرت لـ "خلّي كل رقم يتكرر مرتين بالكتير" (LeetCode 80)، الحل هيبقىnums[read] !== nums[write - 2]، وده مش هيشتغل معread. - بنكتب الرقم الجديد عند
write. ساعاتwrite === readفبيكتب الرقم مكانه، وده مش مشكلة. - الجزء النضيف كبر بعنصر، فالمكان الجاي للكتابة اتحرك.
- بنرجّع
writeلأنه طول الجزء النضيف. اللي بعدwriteفي الـ array مش مهم، والـ judge مش بيبص عليه.
write، وبعد الـ loop تملا الباقي أصفار. Remove Element: بتكتب كل رقم مش بيساوي val. الشرط بس هو اللي بيتغيّر، والهيكل واحد.
فاضل نوع تالت: الاتنين بيمشوا في نفس الاتجاه، بس بسرعات مختلفة.
النوع التالت: سريع وبطيء
الاتنين بيبدأوا من نفس المكان، بس fast بيمشي خطوتين و slow خطوة واحدة. النوع ده مستخدم أكتر مع الـ linked list، وهنفصّله هناك، بس خد الفكرة من دلوقتي:
- نص الـ list: لما
fastيوصل للآخر،slowبيبقى مشي نص المسافة، يعني واقف في النص بالظبط. - فيه دايرة؟ لو الـ list فيها loop، الـ
fastهيلف ويحصّل الـslowمن ورا. زي اتنين بيجروا على تراك دايري، الأسرع لازم يحصّل الأبطأ.
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
عندك string. شيل منه أي حاجة مش حرف أو رقم، وتجاهل الفرق بين الحروف الكبيرة والصغيرة. هل يتقري زي ما هو من الناحيتين؟
نفكّر فيها مع بعض
- افهم المطلوب: مش هنقارن الـ string زي ما هو. هنتجاهل المسافات والعلامات، والـ
Nزي الـn. - أول حل بييجي في دماغك: نعمل string نضيف (حروف وأرقام بس، lowercase)، ونقارنه بمقلوبه. ده O(n) في الوقت، بس بيعمل نسختين جداد، يعني O(n) memory. حل كويس، وقوله في الانترفيو كبداية.
- نقدر نوفّر الـ memory؟ الـ palindrome معناه إن أول حرف زي آخر حرف، والتاني زي اللي قبل الآخر، وهكذا. يعني مقارنة من الطرفين، two pointers من غير ما نعمل أي string جديد: O(1) memory.
- المشكلة الوحيدة: العلامات. لما pointer يقف على علامة أو مسافة، نفوّتها لحد ما يقف على حرف أو رقم.
- الحالات الطرفية: string فاضي أو كله علامات (الإجابة true)، حرف واحد (true)، وحروف كبيرة وصغيرة مع بعض.
- نفس بداية القالب: واحد من الأول وواحد من الآخر.
- الـ
<هنا مش بس عشان ما نقارنش الحرف بنفسه. لما يتقابلوا يبقى خلاص قارنّا كل الأزواج. وفي string طوله فردي، الحرف اللي في النص مالوش حد يتقارن بيه، وأي حرف لوحده palindrome أصلًا. - ليه
left < rightمكررة جوه الـ while الداخلية؟ لو الـ string كله علامات زي"!!!"، الـleftهيفضل يزيد ويعدّيrightويخرج برا الـ string، وs[left]هتبقىundefined، وبعدها.toLowerCase()علىundefinedهيضرب error. الشرط ده بيوقفه في الوقت الصح. - نفس الكلام من الناحية التانية.
- بنحوّل الاتنين لـ lowercase قبل المقارنة، عشان
'N'و'n'يتحسبوا نفس الحرف. ولو مختلفين يبقى مش palindrome، ونرجّع false على طول من غير ما نكمّل. - الزوج ده تمام، فبنقرّب الاتنين خطوة. لازم الاتنين يتحرّكوا. لو نسيت واحد، هتقارن نفس الحرف بحرف جديد والنتيجة هتبقى غلط.
- لو الـ loop خلصت من غير ما نلاقي اختلاف، يبقى palindrome.
/[a-z0-9]/iregex معناها: حرف من 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
عندك حيطان طولها height[i]، وكل حيطة واقفة عند index i. اختار حيطتين يحبسوا أكبر كمية مية. المية مستواها بيبقى قد الحيطة الأقصر، وعرضها هو المسافة بين الحيطتين.
نفكّر فيها مع بعض
- المساحة =
min(height[i], height[j]) × (j - i). الحيطة الأقصر هي اللي بتحدد الارتفاع. - Brute force: جرّب كل زوج، O(n²). ومع
nلحد 10⁵ هياخد TLE. - نبدأ بأعرض حاجة:
left = 0وright = n - 1. ده أكبر عرض ممكن. بعد كده كل حركة هتقلّل العرض 1، فالمكسب الوحيد الممكن إن الارتفاع يزيد. - نحرّك مين؟ دي أهم نقطة. لو حرّكت الحيطة الأطول، الارتفاع عمره ما هيزيد، لأن الأقصر لسه موجودة وهي اللي بتحدّد. والعرض قلّ. يعني المساحة هتقل أو تفضل زي ما هي. لكن لو حرّكت الأقصر، ممكن نلاقي حيطة أطول ترفع المستوى.
- الإثبات: الحيطة الأقصر، مع أي حيطة تانية جوه الرينج، مساحتها أقل من أو تساوي المساحة اللي حسبناها حالًا، لأن العرض أصغر والارتفاع مش هيعدّي طولها. فخلاص جرّبنا أحسن حاجة ليها، ونقدر نشيلها.
- نبدأ من أعرض container ممكن.
best = 0لأن أقل مساحة ممكنة صفر. ما بنحطش-Infinityلأن المساحة عمرها ما بتبقى سالبة.<عشان container محتاج حيطتين مختلفتين. حيطة لوحدها عرضها صفر.- المستوى = الحيطة الأقصر.
Math.minمشMath.max، لأن المية بتدلق من فوق الحيطة الأقصر. - العرض =
right - left، مشright - left + 1. إحنا بنقيس المسافة بين حيطتين، مش بنعدّ عناصر. الحيطة عند 1 والحيطة عند 8 المسافة بينهم 7. الـ +1 بيبقى لما بتعدّ عناصر subarray زي في الـ sliding window. فرّق بين الاتنين. - بنحدّث أحسن مساحة شفناها.
- نحرّك الأقصر. ولو الاتنين متساويين بيدخل في الـ
elseويحرّكright. ده صح، وكان ينفع نحرّك أي واحد، لأن لو الاتنين متساويين، أي حيطة جوه الرينج مع واحدة منهم مش هتدّي مساحة أكبر من اللي حسبناها. فالاتنين خلاص "استهلكوا" فرصتهم.
التعقيد: كل لفة بتحرّك pointer واحد خطوة، والاتنين بيتقابلوا بعد n - 1 خطوة بالكتير. يعني O(n) وقت و O(1) memory.
طب لو المطلوب 3 أرقام مش 2؟ هنرجّع المسألة لحاجة حليناها خلاص.
مثال محلول 3: 3Sum
طلّع كل الـ triplets المختلفة اللي مجموعها صفر. الـ triplet الواحدة ما تتكررش في الإجابة.
نفكّر فيها مع بعض
- Brute force: تلات loops، O(n³). ومع
n = 3000(الـ constraint في LeetCode) ده 27 مليار عملية تقريبًا. مستحيل. - نحوّلها لمسألة نعرفها: لو ثبّتنا الرقم الأول
nums[i]، المطلوب يبقى رقمين مجموعهم-nums[i]. دي مسألة الـ pair sum اللي حليناها فوق، بس محتاجة array مترتبة. - فنرتّب الأول: O(n log n). الترتيب هنا مش بيبوّظ حاجة، لأن المطلوب الأرقام نفسها مش الـ indices.
- لكل
iنعمل two pointers على اللي بعده:left = i + 1وright = n - 1. ده O(n) لكلi، فالمجموع O(n²). أحسن بكتير من O(n³). - الصعب الحقيقي: التكرار.
[-1, -1, 2]ما ينفعش تطلع مرتين. والحل في 3 أماكن: نفوّتiلو رقمها زي اللي قبلها، وبعد ما نلاقي triplet نفوّت الأرقام المكررة عندleftوعندright.
- أخطر سطر في الحل.
nums.sort()من غير comparator في JS بيرتّب الأرقام كأنها نصوص:[-1, -4, 10, 2].sort()بتطلع[-1, -4, 10, 2]، لأنها بتقارن الحروف"-"و"1". الـ(a, b) => a - bمعناها: لو الناتج سالب يبقىaقبلb. ولو نسيته، الـ two pointers هتشتغل على array مش مترتبة فعلًا، والإجابات هتبقى غلط من غير أي error. - ليه
nums.length - 2؟ لأنiمحتاج اتنين بعده (leftوright). لوiوصل لآخر عنصرين، مش هيلاقي اتنين بعده. ممكن تكتبi < nums.lengthوالحل هيشتغل، لأن الـ while الداخلية مش هتدخل، بس- 2أوضح. - ليه
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. - الـ two pointers بيبدأوا من بعد
i، عشان ما نستخدمش نفس العنصر مرتين، وعشان الأزواج اللي قبلiاتجرّبت خلاص. - مجموع التلاتة. لو مستنّي أرقام كبيرة جدًا، خلي بالك من الـ overflow في لغات تانية. في JS الأرقام لحد
2⁵³مضمونة. - لقينا triplet فبنسجّلها. وبنحط القيم مش الـ indices.
- بنحرّك الاتنين، لأن لو حرّكنا واحد بس، المجموع هيتغيّر ومش هيرجع صفر بنفس الـ pointer التاني، إلا لو الرقم مكرر، وده اللي السطرين الجايين بيفوّتوه.
- بنفوّت أي رقم زي اللي لسه سايبينه، عشان ما نطلّعش نفس الـ triplet تاني. والـ
left < rightعشان ما نعدّيش بعض. - نفس الفكرة من اليمين. لاحظ إننا بنقارن بـ
right + 1لأنrightاتحرك لورا، فاللي سبناه بقى على يمينه. - نفس قرار الـ pair sum بالظبط: أصغر من الهدف يبقى نكبّر من الشمال، وأكبر يبقى نصغّر من اليمين.
التعقيد: الـ sort O(n log n)، والـ loop O(n) مرات two pointers O(n)، يعني O(n²) في المجموع. والـ memory O(1) غير الإجابة، أو O(log n) حسب الـ sort.
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].
تمرين: فكّر قبل ما تفتح
array مترتبة وفيها أرقام سالبة. رجّع مربعاتها مترتبة. هل تقدر في O(n) من غير sort؟
تلميح 1
أكبر مربع فين؟ مش في النص أكيد. يا في أول الـ array (سالب كبير) يا في آخرها (موجب كبير).
تلميح 2
two pointers من الطرفين. قارن المربعين، والأكبر حطه في آخر الـ result وحرّك الـ pointer بتاعه. يعني بتملا الإجابة من الآخر للأول.
الحل
هنا left <= right ضمنيًا، لأن الـ loop بتلف n مرة بالظبط، وآخر عنصر بيتحط لما left === right. هنا مسموح الاتنين يقفوا على نفس العنصر، لأننا مش بنعمل زوج، بنحط كل عنصر مرة واحدة.
لو الأسئلة دي عدّت معاك، روح على LeetCode بالترتيب اللي تحت.
اتمرن على LeetCode بالترتيب
حلها بالترتيب ده، كل مسألة بتضيف فكرة واحدة جديدة. علّم على اللي خلّصته، والتقدّم بيتحفظ. لو قعدت أكتر من 25 دقيقة على مسألة، ارجع للقالب بتاعها هنا، وبعدين حاول تاني من غير ما تبص.
- Valid Palindromeالمثال المحلول. اكتبه من دماغك من غير ما تبص.
- Reverse Stringأبسط شكل من الطرفين: swap وقرّب. سخّن بيه إيدك.
- Two Sum IIالقالب الأول بالظبط. خلي بالك إن الإجابة 1-indexed.
- Remove Duplicates from Sorted Arrayالقالب التاني: read و write.
- Move Zeroesread و write بشرط مختلف، وبعدين املا الباقي أصفار.
- Squares of a Sorted Arrayالتمرين اللي فوق: تملا من الآخر.
- Container With Most Waterالمثال المحلول 2. اشرح الإثبات لنفسك بصوت عالي.
- 3Sumsort وبعدين pair sum جوه loop، والتكرار هو التحدي.
- Sort Colorsتلات pointers (Dutch flag). خطوة لقدّام في نفس الفكرة.
- Remove Duplicates IIهنا تفهم ليه بنقارن بـ
write - 2. - Trapping Rain Waterاختياري: من الطرفين مع max من كل ناحية. لو حليتها يبقى فهمت الـ 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 بيصغّرها لما تبقى غلط. كل اللي اتعلمته هنا عن "مين يتحرك وليه" هتستخدمه هناك على طول.