Two pointers ও sliding window — প্রতিটি অবস্থার ছবি

Sorted array-এ target 11

বড় যোগে R বাঁয়ে, ছোট যোগে L ডানে

1. ১. দুই প্রান্তের যোগ 12

   চিহ্নিত ঘর: 01↑ L

   12

   24

   37

   49

   চিহ্নিত ঘর: 511↑ R

   1 + 11 > 11; R এক ঘর বাঁয়ে আনি।

2. ২. এখন যোগ 10

   চিহ্নিত ঘর: 01↑ L

   12

   24

   37

   চিহ্নিত ঘর: 49↑ R

   ফাঁকা বা বাদ দেওয়া ঘর: 511

   1 + 9 < 11; L এক ঘর ডানে নিই।

3. ৩. জোড়া পাওয়া গেছে

   ফাঁকা বা বাদ দেওয়া ঘর: 01

   চিহ্নিত ঘর: 12↑ L

   24

   37

   চিহ্নিত ঘর: 49↑ R

   ফাঁকা বা বাদ দেওয়া ঘর: 511

   2 + 9 = 11। ম্লান ঘরগুলো অনুসন্ধান থেকে আগেই বাদ গেছে।

কেন প্রথম ধাপে 11 বাদ দেওয়া নিরাপদ? সবচেয়ে ছোট মান 1 দিয়েও যোগ বেশি; 11-এর সঙ্গে অন্য কোনো বেঁচে থাকা মান নিলে যোগ আরও বাড়বে।

Sum অন্তত 7: সবচেয়ে ছোট positive window

Array [2,3,1,2,4,3]; প্রতিবার ডানে একটি মান যোগ করি, sum যথেষ্ট থাকলে বাঁ থেকে ছোট করি।

নতুন R	সব পর্যবেক্ষিত valid window	shrink শেষে window	best দৈর্ঘ্য
0, মান 2	নেই	[2]	নেই
1, মান 3	নেই	[2,3]	নেই
2, মান 1	নেই	[2,3,1]	নেই
3, মান 2	[2,3,1,2], sum 8	[3,1,2], sum 6	4
4, মান 4	[3,1,2,4], sum 10; [1,2,4], sum 7	[2,4], sum 6	3
5, মান 3	[2,4,3], sum 9; [4,3], sum 7	[3], sum 3	2

flowchart LR
    A["R ডানে: একটি মান যোগ"] --> B{"sum অন্তত 7?"}
    B -->|"হ্যাঁ"| C["best রাখি, বাঁয়ের মান বাদ, L বাড়াই"]
    C --> B
    B -->|"না"| D["পরের R"]

প্রতিটি pointer শুধু ডানে চলে; তাই মোট pointer move O(n)। Negative মান যোগ হলে sum কমতেও পারে—তখন এই প্রমাণ প্রযোজ্য নয়।

Exactly 2 distinct: [1,2,1,3]

গণনা	প্রতিটি R-এ নতুন valid subarray সংখ্যা	মোট
atMost(2)	1,2,3,2	8
atMost(1)	1,1,1,1	4
exactly(2)	atMost(2) − atMost(1)	4

সেই চারটি subarray: [1,2], [2,1], [1,2,1], [1,3]। সব একই value হলেও আলাদা index interval হলে আলাদা subarray হিসেবে গুনতে হয়।

একই দিকে দুই pointer: difference 3

Sorted array [1,2,4,7]।

i	j	a[j]−a[i]	সিদ্ধান্ত
0	1	1	j বাড়াই
0	2	3	(1,4) পাওয়া গেছে

Difference বেশি হলে i বাড়িয়ে ছোট করার চেষ্টা করি; তবে i<j রাখতে হবে। Unsorted array-এ মানের এই monotonic যুক্তি নেই।

Container: ছোট দেয়াল কেন সরাই

দেয়ালের উচ্চতা ও দুই প্রান্তের পছন্দ

1. প্রথম দুই দেয়াল

   চিহ্নিত ঘর: 01↑ L

   14

   22

   চিহ্নিত ঘর: 33↑ R

   ছোট উচ্চতা 1, দূরত্ব 3: area = 3।

2. ছোট দেয়ালটি সরাই

   ফাঁকা বা বাদ দেওয়া ঘর: 01

   চিহ্নিত ঘর: 14↑ L

   22

   চিহ্নিত ঘর: 33↑ R

   ছোট উচ্চতা এখন 3, দূরত্ব 2: area = 6।

প্রথম area min(1,3)×3=3। ডানের দেয়াল সরালে width কমবে, উচ্চতা এখনও সর্বোচ্চ 1—উন্নতি হবে না। বাঁয়ের ছোট দেয়াল সরালে নতুন area min(4,3)×2=6 হতে পারে।

r-l+1 কোথা থেকে আসে

Valid window [1,2,1]-এ r=2, l=0 হলে r-এ শেষ হওয়া সব suffix: [1,2,1], [2,1], [1]—মোট 3। At-most-distinct শর্তে এগুলো সব valid। Minimum-sum শর্তে ছোট suffix valid নাও হতে পারে, তাই এই count নির্বিচারে ব্যবহার করা যাবে না।

ধারণায় ফিরি · সব সমস্যা ও অনুশীলন · মূল উৎস