Skip to content

Problems — Level 6: Two Pointers ও Sliding Window

এই folder-এ Level 6-এর 10টা problem-এর note থাকবে। প্রতিটার জন্য আলাদা .md file — নিজের ভাষায় problem বোঝা, pointer/window-র film strip, dry run, code আর ভুল থেকে শেখা।

কীভাবে problem গুলো use করবে?

প্রতিটা problem-এর note লেখা হয় ../../../templates/math-problem-note-template.md follow করে — ২০টা section-এর template: problem বোঝা → brute force → optimization → dry run → complexity → "ভবিষ্যতের আমাকে এক লাইনে কী বলব"। শুরুতে template-টা একবার পড়ে নাও।

নিয়মটা সহজ:

  1. Table থেকে problem নাও (recommended order ../README.md-তে)
  2. আগে O(n²) brute force লিখে ফেলো — তারপর জিজ্ঞেস করো "কোন তথ্যটা থাকলে ভেতরের loop-এ ফিরতে হতো না?" — সেটাই pointer/window-র জায়গা
  3. Dry run-এ প্রতি step-এ l, r আর invariant-এর মান টেবিলে লেখো
  4. Solve হলে Status planned → done

Tracker table

# Problem Difficulty Pattern Inherits from Source Note file Status
081 Two Sum Sorted Easy opposite pointers 073 LeetCode Two Sum II — https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/, CSES Sum of Two Values — https://cses.fi/problemset/task/1640 081-two-sum-sorted.md planned
082 Pair with Difference K Medium same-direction pointers 081 LeetCode K-diff Pairs — https://leetcode.com/problems/k-diff-pairs-in-an-array/ 082-pair-with-difference-k.md planned
083 Three Sum Medium fix + two pointers 081 LeetCode 3Sum — https://leetcode.com/problems/3sum/ 083-three-sum.md planned
084 Container With Most Water Medium move shorter wall 081 LeetCode — https://leetcode.com/problems/container-with-most-water/ 084-container-with-most-water.md planned
085 Sliding Window Sum Easy fixed window 067 Classic exercise 085-sliding-window-sum.md planned
086 Longest Subarray with Sum K (Positive) Medium grow/shrink window 085 Classic exercise 086-longest-subarray-sum-k.md planned
087 Minimum Size Subarray Sum Medium shrinkable window 086 LeetCode — https://leetcode.com/problems/minimum-size-subarray-sum/ 087-minimum-size-subarray-sum.md planned
088 Count Subarrays with At Most K Distinct Medium window + count map 086 LeetCode Fruit Into Baskets (K=2 version) — https://leetcode.com/problems/fruit-into-baskets/ 088-at-most-k-distinct.md planned
089 Count Subarrays with Exactly K Distinct Hard atMost(K)−atMost(K−1) 088 LeetCode Subarrays with K Different Integers — https://leetcode.com/problems/subarrays-with-k-different-integers/ 089-exactly-k-distinct.md planned
090 Number of Subarrays with Product Less Than K Medium window count r−l+1 087 LeetCode Subarray Product Less Than K — https://leetcode.com/problems/subarray-product-less-than-k/ 090-product-less-than-k.md planned

"Inherits from" column-টা কী?

প্রতিটা problem আগের কারো কাঁধে দাঁড়িয়ে। 081 নিজে দাঁড়িয়ে আছে Level 5-এর 073-এর উপর (Two Sum-এর hash পথ vs sorted-এ pointer পথ — তুলনাটাই শিক্ষা)। 081 থেকে তিন শাখা: ধাওয়া (082), fix (083), greedy দেয়াল (084)। Window শাখা শুরু 085 থেকে, আর 089 দাঁড়িয়ে 088-এর কাঁধে।

[Level 5: 073 prefix+hash] ──> 081 (opposite pointers)
                                  ├──> 082 (same-direction)
                                  ├──> 083 (fix + two pointers)
                                  └──> 084 (container, প্রমাণসহ greedy)

[Level 5: 067 prefix] ──> 085 (fixed window)
                            └──> 086 (grow/shrink) ──> 087 (min size)
                                    │                     └──> 090 (count r−l+1)
                                    └──> 088 (at most K) ──> 089 (exactly K)

একটা ছোট পরামর্শ

এই level-এর প্রতিটা problem-এ নিজেকে দুটো প্রশ্ন করো: "কোন move-টা নিরাপদ, আর কেন?" এবং "আমার invariant-টা ঠিক কী?" প্রথমটার উত্তর না জেনে pointer সরালে সেটা মুখস্থ — interview-তে variation এলেই ধরা। আর মনে রেখো এই হাতিয়ারের সীমা আছে: negative number এলে window-র যুক্তি ভাঙে, তখন Level 5-এর prefix + hash map-ই ভরসা। কোন problem-এ কোন হাতিয়ার — এই বিচারটাই আসল দক্ষতা।

Concept ঝালাই করতে → ../concept-notes.md। ছবি এঁকে বুঝতে → ../visualization-ideas.md।