Two Pointers and Safe Candidate Elimination
آمادگی مصاحبهٔ الگوریتمی با Python
- In 60 minutes, recognize problems where two positions delimit candidates and a comparison safely eliminates some of them.
- Clarify whether order must be preserved and whether sorting is permitted; distinguish moving inward from scanning both positions forward.
- Independently propose which pointer to move for Container With Most Water before seeing the elimination argument.
- Develop the problem from enumerating every pair to an inward two-pointer Python solution.
- Prove that discarding the shorter boundary cannot discard a better pair involving that boundary; explain termination and O(n) time with O(1) auxiliary space.
- Test two elements, equal heights, repeated heights, and zero heights; diagnose moving the taller pointer and confusing the pattern with arbitrary pair search.
- Identify unsuitable uses when no ordering or dominance argument supports discarding candidates.
مساحت، همهٔ جفتها و ترتیب اصلی
Container With Most Water
\(n\ge 2,\quad h_i\ge 0,\quad 0\le i<j<n\)
فاصلهٔ جایگاههای مجاور: \(1\)؛ خروجی: فقط بیشترین مساحت. خطهای میانی مانع نیستند.
**فاصله × ارتفاع کوتاهتر**
\[ A(i,j)=(j-i)\min(h_i,h_j) \]
ترتیب اصلی جایگاهها باید حفظ شود.
**Brute Force؛ جفت اول**
\[ h=[1,2,4,3],\qquad A(0,1)=(1-0)\min(1,2)=1\times1=1 \]
**جفت بعدی**
\[ A(0,2)=(2-0)\min(1,4)=2\times1=2 \]
**جفت بعدی**
\[ A(0,3)=(3-0)\min(1,3)=3\times1=3 \]
**جفت بعدی**
\[ A(1,2)=(2-1)\min(2,4)=1\times2=2 \]
**جفت بعدی**
\[ A(1,3)=(3-1)\min(2,3)=2\times2=4 \]
**آخرین جفت**
\[ A(2,3)=(3-2)\min(4,3)=1\times3=3 \]
**بیشترین مساحت**
\[ \max\{1,2,3,2,4,3\}=4 \]
**دو حلقه و نگهداری بیشترین مساحت**
\[ \sum_{i=0}^{n-2}(n-i-1)=\frac{n(n-1)}{2},\qquad T(n)=O(n^2),\quad S_{\mathrm{aux}}(n)=O(1) \]
برای هر جایگاه اول، فقط جایگاههای بعدی بررسی میشوند.
**مرتبسازی، دادهٔ مسئله را عوض میکند**
\[ \begin{aligned}h&=[1,2,4,3]\\h'&=[1,2,3,4]\\A'(1,3)&=(3-1)\min(2,4)=4\\A'(2,3)&=(3-2)\min(3,4)=3\end{aligned} \]
ارتفاعهای جایگاههای پایانی عوض شدهاند؛ یکسان ماندن جواب، حفظ مسئلهٔ اصلی نیست.
چرا حذف مرز کوتاهتر امن است؟
```svg
<svg viewBox="0 0 800 450" xmlns="http://www.w3.org/2000/svg"><text x="400" y="40" text-anchor="middle" class="tm-text" font-size="22" direction="rtl">کدام مرز را کنار میگذاریم؟</text><rect x="168" y="245" width="342" height="40" class="tm-soft"/><path d="M120 285 H540" class="tm-line"/><rect x="150" y="245" width="18" height="40" rx="3" class="tm-accent"/><rect x="270" y="205" width="18" height="80" rx="3" class="tm-soft"/><rect x="390" y="125" width="18" height="160" rx="3" class="tm-soft"/><rect x="510" y="165" width="18" height="120" rx="3" class="tm-accent"/><text x="159" y="233" text-anchor="middle" class="tm-text" font-size="20">1</text><text x="279" y="193" text-anchor="middle" class="tm-text" font-size="20">2</text><text x="399" y="113" text-anchor="middle" class="tm-text" font-size="20">4</text><text x="519" y="153" text-anchor="middle" class="tm-text" font-size="20">3</text><text x="159" y="315" text-anchor="middle" class="tm-muted" font-size="17">0</text><text x="279" y="315" text-anchor="middle" class="tm-muted" font-size="17">1</text><text x="399" y="315" text-anchor="middle" class="tm-muted" font-size="17">2</text><text x="519" y="315" text-anchor="middle" class="tm-muted" font-size="17">3</text><text x="159" y="352" text-anchor="middle" class="tm-text-accent" font-size="18" direction="rtl">چپ</text><text x="519" y="352" text-anchor="middle" class="tm-text-accent" font-size="18" direction="rtl">راست</text><path d="M168 245 H510" class="tm-line-accent" stroke-width="3"/><text x="650" y="235" text-anchor="middle" class="tm-text-accent" font-size="18" direction="rtl">سقف ارتفاع: مرز چپ</text><text x="400" y="395" text-anchor="middle" class="tm-text" font-size="20" direction="rtl">اول ثبت مساحت؛ بعد حذف</text><path d="M159 75 H399 M159 70 V80 M399 70 V80 M159 95 H279 M159 90 V100 M279 90 V100" class="tm-line-accent" stroke-width="2"/><text x="650" y="285" text-anchor="middle" class="tm-text" font-size="18" direction="rtl">عرض کمتر؛ سقف همان</text><path d="M140 290 L178 240 M190 335 H260 L250 328 M260 335 L250 342" class="tm-line-accent" stroke-width="3"/><text x="650" y="345" text-anchor="middle" class="tm-text-green" font-size="20" direction="rtl">حذف چپ امن است</text><text x="400" y="432" text-anchor="middle" class="tm-text-green tm-enter" font-size="18" direction="rtl">بهینه: یا ثبت شده، یا هنوز بین مرزهای باقیمانده است</text></svg>
```
از حذف امن تا کد خطی
**پیادهسازی Python**
```python
def maxarea(height):
left = 0
right = len(height) - 1
best = 0
while left < right:
width = right - left
shorter = min(height[left], height[right])
area = width * shorter
best = max(best, area)
if height[left] <= height[right]:
left += 1
else:
right -= 1
return best
```
**ترتیب ضروری:** حساب مساحت ← ثبت جواب ← حذف امن مرز کوتاهتر. دستور `return` بیرون حلقه است.
**پایان حلقه و هزینه** — با \(n=\operatorname{len}(\texttt{height})\) و \(n\geq 1\):
\[
d=\texttt{right}-\texttt{left},\qquad d_0=n-1,\qquad d_{k+1}=d_k-1
\]
\[
d_k=n-1-k=0\ \Longrightarrow\ k=n-1
\]
هر دور کار ثابت دارد؛ فقط چند متغیر نگه داشته میشود:
\[
T(n)=O(n),\qquad S_{\mathrm{aux}}(n)=O(1)
\]
**Brute Force:** همین محاسبه و ثبت جواب، داخل دو حلقهٔ `for` برای همهٔ جفتهای \(0\leq i<j<n\).
حذف امن و حذف اشتباه
| قاعده | \((left,right)\) | ارتفاعهای دو مرز | عرض | مساحت | \(best\) |
| --- | --- | --- | --- | --- | --- |
| حذف کوتاهتر | \((0,3)\) | \((1,3)\) | \(3\) | \(3\times1=3\) | \(0\to3\) |
| جفتِ ازدسترفته در روش غلط | \((1,3)\) | \((2,3)\) | \(2\) | \(2\times2=4\) | \(3\to4\) |
| حذف کوتاهتر | \((2,3)\) | \((4,3)\) | \(1\) | \(1\times3=3\) | \(4\) |
| پایان؛ \(3\) بررسی بهجای \(6\) | \((2,2)\) | — | \(0\) | — | \(4\) |
| حذف بلندتر | \((0,3)\) | \((1,3)\) | \(3\) | \(3\times1=3\) | \(0\to3\) |
| حذف بلندتر | \((0,2)\) | \((1,4)\) | \(2\) | \(2\times1=2\) | \(3\) |
| حذف بلندتر | \((0,1)\) | \((1,2)\) | \(1\) | \(1\times1=1\) | \(3\) |
| پایان؛ جواب غلط | \((0,0)\) | — | \(0\) | — | \(3\) |
تست مرزها و دفاع از حذف
سه ورودی: \([2,5]\)، \([2,2,2]\)، \([0,0,0]\)
در هر گام: \(A=(r-l)\min(h_l,h_r)\)؛ ثبت best پیش از حرکت.
**دو عضو؛ سپس پایان**
\[ [2,5]:\quad (l,r)=(0,1),\quad A=1\times2=2,\quad \mathrm{best}=2 \]
پس از ثبت مساحت، چپ حرکت میکند: \(l=r=1\)؛ پایان.
**ارتفاعهای برابر؛ جفت اول**
\[ [2,2,2]:\quad (l,r)=(0,2),\quad A=2\times2=4,\quad \mathrm{best}=4 \]
قرارداد برابری: حرکت چپ؛ \(l=1\). حرکت راست هم امن بود.
**ارتفاعهای برابر؛ جفت دوم و پایان**
\[ (l,r)=(1,2),\quad A=1\times2=2,\quad \mathrm{best}=\max(4,2)=4 \]
حرکت چپ: \(l=r=2\)؛ پاسخ \(4\).
**همه صفر؛ جفت اول**
\[ [0,0,0]:\quad (l,r)=(0,2),\quad A=2\times0=0,\quad \mathrm{best}=0 \]
حرکت چپ: \(l=1\).
**همه صفر؛ جفت دوم و پایان**
\[ (l,r)=(1,2),\quad A=1\times0=0,\quad \mathrm{best}=0 \]
حرکت چپ: \(l=r=2\)؛ پاسخ صفر است، نه الزاماً مثبت.
**جفتها کافی نیستند**
\[ \text{pairs}\;\not\Rightarrow\;O(n) \]
برای Two Pointers، ترتیب یا دلیل برتری باید حذف نامزدها را امن کند.
**دو جایگاه، نه دو حلقهٔ مستقل**
\[ \#\mathrm{moves}=n-1\quad\Longrightarrow\quad T(n)=O(n) \]
معیار، مجموع حرکتهاست؛ نه تعداد جایگاهها.
**ترتیب اصلی حفظ میشود**
\[ A(i,j)=(j-i)\min(h_i,h_j) \]
مرتبسازی مجاز نیست: فاصلهٔ اصلی در جواب اثر دارد. دفاع مصاحبه: چرا نامزد حذفشده لازم نیست؟
Back to course