# Hard Patterns — The Cross-Topic Combo Dictionary

[অধ্যায়ের সূচি](README.md) · [সহজ ব্যাখ্যা ও বাস্তব ব্যবহার](learning-guide.md) · [অনুশীলন ও সমাধান](problems/README.md)

> Hard problem কালেভদ্রে কোনো *নতুন* tool। তারা আসলে হাত-ধরাধরি করা দুটো চেনা tool। এই file নাম দিয়েছে সেই আটটা combo-কে, যারা বেশিরভাগ hard interview আর contest problem cover করে — সাথে recognition signal, যাতে প্রত্যেকটা cold অবস্থায় চিনে ফেলতে পারো।

প্রতিটা combo-র জন্য: যে signal-গুলো দেখে সন্দেহ করবে, tool দুটোকে জোড়া দেওয়া এক-বাক্যের thinking tweak, example problem, আর কোন repo folder থেকে সে উত্তরাধিকার পায়।

---

## 1. Binary search on the ANSWER + greedy feasibility check

- **Recognition signals:** "minimize the maximum ___" বা "maximize the minimum ___"; উত্তরটা একটা জানা range-এর ভেতরের একটামাত্র সংখ্যা; যেকোনো guessed value-র জন্য "এটা কি achievable?" check করা optimum সরাসরি compute করার চেয়ে সহজ; feasibility-টা *monotonic* (X কাজ করলে X-এর চেয়ে সহজ সবকিছুই কাজ করে)।
- **The thinking tweak:** উত্তর খোঁজা বন্ধ করো — উত্তরটা **guess** করো, আর guess-টাকে binary-search করো। কঠিন optimization problem-টা হয়ে যায় log(range)-টা সহজ yes/no প্রশ্ন, প্রত্যেকটার উত্তর দেয় একটা greedy বা linear check।
- **Example problems:**
  - একটা array-কে k ভাগে ভাঙা, সবচেয়ে বড় ভাগের sum minimize করে — [LeetCode · Split Array Largest Sum](https://leetcode.com/problems/split-array-largest-sum/)।
  - খাওয়ার speed-এর problem ("slowest speed that still finishes in time") — [LeetCode · Koko Eating Bananas](https://leetcode.com/problems/koko-eating-bananas/)।
- **Inherits from:** binary search ([পূর্বশর্ত](../01-math-based-programming-fundamentals/07-binary-search-on-answer/README.md)), greedy reasoning (এই পাতার greedy feasibility check), monotonicity-র intuition।

## 2. Sliding window + hashmap

- **Recognition signals:** "longest/shortest substring or subarray satisfying ___"; property-টা character বা element-এর *count* জড়ায় ("contains all of", "at most k distinct"); window বাড়ালে/কমালে property-টা monotone আচরণ করে।
- **The thinking tweak:** Window-র দুটো pointer সামলায় *কোথায়*; hashmap সামলায় *ভেতরে কী আছে*। ডান প্রান্ত greedily বাড়াও; বাঁ প্রান্ত গোটাও শুধু যতক্ষণ invariant ভাঙা থাকে (বা, "shortest containing"-এর ক্ষেত্রে, যতক্ষণ সেটা টিকে থাকে)।
- **Example problems:**
  - [Minimum Window Substring (LeetCode 76)](https://leetcode.com/problems/minimum-window-substring/) — সব দরকারি character cover করা shortest window।
  - [Longest Substring Without Repeating Characters (LeetCode 3)](https://leetcode.com/problems/longest-substring-without-repeating-characters/)।
- **Inherits from:** sliding window ([../02-arrays-and-strings/](../02-arrays-and-strings/README.md)), frequency hashmap ([../05-hashing/](../05-hashing/README.md))।

## 3. Heap + intervals

- **Recognition signals:** start/end time-ওয়ালা event; "how many simultaneous ___", "minimum rooms/machines/servers"; event-গুলো time order-এ process করো আর সবসময় জানতে হয় active জিনিসগুলোর মধ্যে *earliest-ending*-টা কোনটা।
- **The thinking tweak:** Interval-গুলো start দিয়ে sort করো (timeline-টা), আর **end time**-গুলোর একটা min-heap রাখো (active set-টা)। প্রতিটা নতুন interval-এ, পেরিয়ে-যাওয়া প্রতিটা end time pop করো — heap-এর size-ই হলো live concurrency।
- **Example problems:**
  - Minimum meeting rooms — [LeetCode · Meeting Rooms II](https://leetcode.com/problems/meeting-rooms-ii/) (premium)।
  - [Merge k Sorted Lists (LeetCode 23)](https://leetcode.com/problems/merge-k-sorted-lists/) — সেই একই "always need the smallest frontier" instinct, end time-এর জায়গায় list head।
  - Heap ছাড়া warm-up: [Merge Intervals (LeetCode 56)](https://leetcode.com/problems/merge-intervals/)।
- **Inherits from:** heaps ([../08-heap-priority-queue/](../08-heap-priority-queue/README.md)), sorting আর sweep thinking ([পূর্বশর্ত](../02-arrays-and-strings/README.md))।

## 4. Monotonic stack

- **Recognition signals:** "next greater/smaller element"; "how far can each element see"; histogram, skyline, temperature, দেয়ালের মাঝের পানি — যেখানেই প্রতিটা element-এর উত্তর ঠিক করে তার nearest dominating neighbor।
- **The thinking tweak:** এমন একটা stack রাখো যেটা *construction*-এর গুণেই sorted থাকে: প্রতিটা নতুন element তার dominate করা সবাইকে pop করে (আর ঠিক সেই pop-এর মুহূর্তেই popped element-দের *উত্তর দিয়ে দেয়*)। প্রতিটা element একবার push হয়, একবার pop — ভেতরে loop থাকা সত্ত্বেও মোট O(n)।
- **Example problems:**
  - [Trapping Rain Water (LeetCode 42)](https://leetcode.com/problems/trapping-rain-water/) — canonical দেয়াল-আর-পানির আকৃতি (two pointers দিয়েও হয়; দুটোই জানাটাই flex)।
  - [Daily Temperatures (LeetCode 739)](https://leetcode.com/problems/daily-temperatures/) — খাঁটি next-greater drill।
- **Inherits from:** stacks ([../03-linked-list/](../03-linked-list/README.md) বা এই repo-র stacks-and-queues folder), array scanning ([../02-arrays-and-strings/](../02-arrays-and-strings/README.md))।

## 5. Graph + DP (longest path / counting on a DAG)

- **Recognition signals:** dependency বা একমুখী move (prerequisites, "strictly increasing neighbor", versioned states); চাওয়া হয়েছে *longest* chain বা path-এর *সংখ্যা* — যা একা BFS দিতে পারে না; move-গুলো কখনো loop করতে পারে না (acyclic), বা strict inequality acyclicity-টা জোর করে আনে।
- **The thinking tweak:** একটা DAG-এর topological order হলো ready-made একটা DP fill order। Define করো `dp[v]` = `v`-তে শেষ (বা শুরু) হওয়া উত্তর, vertex-গুলো topological order-এ process করো, আর প্রতিটা edge হয়ে যায় একটা করে transition। Memoized DFS একই order implicitly পায়।
- **Example problems:**
  - [Longest Increasing Path in a Matrix (LeetCode 329)](https://leetcode.com/problems/longest-increasing-path-in-a-matrix/) — grid-টা একটা DAG, কারণ move-এ value strictly বাড়ে।
  - একটা explicit dependency graph-এ path গোনা বা longest path — [CSES · Longest Flight Route](https://cses.fi/problemset/task/1680) / [Game Routes](https://cses.fi/problemset/task/1681)।
- **Inherits from:** graphs + topological sort ([../09-graphs/topological-sort.md](../09-graphs/topological-sort.md)), DP-র state thinking ([../12-dynamic-programming/](../12-dynamic-programming/README.md))।

## 6. Segment tree / BIT for order statistics

- **Recognition signals:** "for each element, how many earlier/later elements are smaller/greater"; "count inversions"; "rank of each element as it arrives"; n 10⁵ পর্যন্ত গেলে O(n²) pair-counting brute force; value হয়তো বিশাল কিন্তু সংখ্যায় মাত্র n-টা।
- **The thinking tweak:** Tree-টাকে position নয়, **value-গুলোর উপর একটা frequency table** হিসেবে ব্যবহার করো। Array-টা এক দিকে scan করো; প্রতিটা element-এ, *query* করো already-seen কতগুলো value একটা range-এ পড়ে, তারপর element-টা *insert* করো। বিশাল value-গুলোকে আগে coordinate-compress করে rank বানাও।
- **Example problems:**
  - [Count of Smaller Numbers After Self (LeetCode 315)](https://leetcode.com/problems/count-of-smaller-numbers-after-self/) — নামটাই এর।
  - [Reverse Pairs (LeetCode 493)](https://leetcode.com/problems/reverse-pairs/) — একই engine, queried range-এ একটা মোচড়।
- **Inherits from:** Fenwick/segment trees ([../11-segment-tree-and-fenwick-tree/](../11-segment-tree-and-fenwick-tree/README.md)), compression-এর জন্য sorting ([পূর্বশর্ত](../02-arrays-and-strings/README.md))।

## 7. DP + bitmask

- **Recognition signals:** n ≤ ~20 (পুরো problem-solving-এর সবচেয়ে জোরালো signal); "use each element exactly once", "visit every city", "assign workers to jobs"; স্বাভাবিক state-টাকে মনে রাখতেই হয় *কোন subset* খরচ হয়ে গেছে।
- **The thinking tweak:** Subset-টা নিজেই হয়ে যায় DP-র state, একটা integer-এর bit হিসেবে encode করা — affordable শুধু এজন্যই যে 2²⁰ ≈ 10⁶। `dp[mask]` (প্রায়ই `dp[mask][last]`), transition-গুলো আর-একটা করে bit set করে। ছোট্ট n কোনো উপহার নয়; এটা একটা নির্দেশ।
- **Example problems:**
  - ≤ 20 শহরের উপর traveling-salesman-ধাঁচের minimum tour (classic; CSES-এ আছে "Hamiltonian Flights" at [cses.fi/problemset](https://cses.fi/problemset/task/1690))।
  - ≤ 16-টা item-কে k-টা সমান দলে ভাগ করা — [LeetCode · Partition to K Equal Sum Subsets](https://leetcode.com/problems/partition-to-k-equal-sum-subsets/)।
- **Inherits from:** DP ([../12-dynamic-programming/patterns.md](../12-dynamic-programming/patterns.md), family 7), bit manipulation (math level 4), subset enumeration (math level 11)।

## 8. Meet-in-the-middle

- **Recognition signals:** n ≈ 30–40 — 2ⁿ-এর জন্য বড় বেশি, DP-র জন্য বড় বেশি unstructured (value astronomically বিশাল, index করার মতো ছোট কোনো capacity নেই); sum/score শর্তসহ "choose any subset"।
- **The thinking tweak:** 2⁴⁰ impossible কিন্তু 2²⁰ সহজ — তাই **set-টা অর্ধেক করো**, প্রতিটা অর্ধেকের সব subset enumerate করো (প্রতিটা 2²⁰), তারপর অর্ধেক দুটোকে জোড়ো sorting + binary search বা two pointers দিয়ে। Exponential খরচটা square-root হয়ে যায়।
- **Example problems:**
  - n ≈ 40 আর value বিশাল হলে sum ≤ / = একটা target-এর subset গোনা — CSES "Meet in the Middle" at [cses.fi/problemset](https://cses.fi/problemset/task/1628)।
  - দুই ভাগে ভাঙা closest subset sum — [LeetCode · Partition Array Into Two Arrays to Minimize Sum Difference](https://leetcode.com/problems/partition-array-into-two-arrays-to-minimize-sum-difference/)।
- **Inherits from:** math level 11-এর subset enumeration আর meet-in-the-middle idea ([../01-math-based-programming-fundamentals/](../01-math-based-programming-fundamentals/README.md)), binary search ([পূর্বশর্ত](../01-math-based-programming-fundamentals/07-binary-search-on-answer/README.md))।

---

## The recognition cheat sheet

| You read... | Suspect combo |
| --- | --- |
| "minimize the maximum" / "maximize the minimum" | 1 — binary search on answer |
| "longest substring with counts condition" | 2 — window + hashmap |
| "minimum rooms / max simultaneous" | 3 — heap + intervals |
| "next greater" / walls / histogram / water | 4 — monotonic stack |
| "longest chain through dependencies / increasing moves" | 5 — graph + DP |
| "for each element, count smaller before/after" | 6 — tree for order statistics |
| "n ≤ 20, use each exactly once" | 7 — DP + bitmask |
| "n ≈ 40, any subset, huge values" | 8 — meet-in-the-middle |

## A worked recognition, start to finish (শুরু থেকে শেষ, একটা কাজে-করা চেনা)

ছদ্মবেশী একটা prompt-এ dictionary-টা fire করতে দেখো:

> "A shipping company must move `n` packages, in the given order, within `d` days. Each day's load is the sum of that day's packages. What is the smallest ship capacity that gets everything delivered on time?"

```text
read 1 (story):  ships, packages, days — operational wrapper, ignore
read 2 (shape):  answer is ONE number (a capacity); "smallest capacity
                 that still works" = minimize a maximum daily load
signal match:    "minimize the maximum" -> combo 1, binary search on answer
monotone check:  if capacity C works, every C+1 works  ✓
feasibility:     given a guessed C, greedily pack days left to right,
                 count days used, compare to d — O(n) per guess
plan:            binary search C over [max(package), sum(packages)],
                 O(n log(sum)) total
```

ত্রিশ সেকেন্ডের signal-matching বদলে দিল সেটাকে, যা নাহলে হতো একটা চালাক idea-র জন্য অন্ধ হাতড়ানো। (এই task-টার public version হলো [LeetCode · Capacity to Ship Packages Within D Days](https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/)।)

## Combos love company: frequent pairings (combo-রা সঙ্গ ভালোবাসে)

Hard problem মাঝেমধ্যে combo-গুলোকে শিকলে গাঁথে। যে জুটিগুলোর জন্য তৈরি থাকা উচিত:

- **1 + 3:** একটা time/capacity binary search করো, যেখানে প্রতিটা feasibility check একটা heap দিয়ে interval sweep করে।
- **5 + 6:** এমন একটা DAG-এর উপর DP, যার transition একটা range-এর প্রশ্ন করে — উত্তর দেয় folder 11-এর একটা segment tree (value-গুলোর উপর tree দিয়ে LIS-ও ঠিক এভাবেই O(n log n)-এ পৌঁছায়)।
- **2 + 4:** Window-র problem, যেখানে "window-র ভেতরের best"-এর জন্য hashmap-এর বদলে লাগে একটা monotonic deque।
- **7 + 1:** ছোট set-এর জন্য bitmask DP, আর যে threshold-টা জিজ্ঞেস করা হচ্ছে তার জন্য binary search।

জুটিগুলো আলাদা করে *practice* করতে হবে না — প্রতিটা অর্ধেক চিনতে পারাই যথেষ্ট, কারণ fusion-টা সবসময়ই "এক combo অন্যটার ভেতরের প্রশ্নের উত্তর দেয়"।

## How to drill this file (এই file কীভাবে drill করবে)

1. আটটা combo-ই একবার পড়ো, তারপর এক সপ্তাহ প্রতিদিন শুধু **signals**-এর লাইনগুলো আবার পড়ো।
2. [problems/README.md](problems/README.md)-এর প্রতিটা problem-এর জন্য, statement পড়ার আগে *শুধু title আর constraint থেকে* তোমার combo-আন্দাজটা লেখো। Hit rate track করো; ~70%-এর উপরে মানে dictionary-টা বসে গেছে।
3. আন্দাজ miss করলে problem note-এ এক লাইন লেখো: "আমি X আন্দাজ করেছিলাম কারণ ___; আসলে Y ছিল কারণ ___।" Miss-গুলো hit-এর চেয়ে দ্রুত signal শেখায়।
4. সপ্তাহে একবার [Codeforces problem set](https://codeforces.com/problemset/) বা [CSES](https://cses.fi/problemset/) খোলো, পাঁচটা random statement পড়ো, আর ONLY classify করো — solve নয়। Solve করার চাপ ছাড়া classification-ই সবচেয়ে সস্তা recognition training।
5. যেকোনো জায়গায় যেকোনো hard problem-এ আটকালে, হতাশ হওয়ার আগে cheat sheet-টা উপর থেকে নিচে checklist হিসেবে চালাও। "আটটার একটাও মেলে না" বিরল — আর সত্যি হলে সাধারণত মানে problem-টা ভয়ের পোশাক-পরা একটা single-tool problem।