Skip to content

Hard Patterns — The Cross-Topic Combo Dictionary

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" at leetcode.com।
  • খাওয়ার speed-এর problem ("slowest speed that still finishes in time") — LeetCode "Koko Eating Bananas" at leetcode.com।
  • Inherits from: binary search (../03-searching-and-sorting/), greedy reasoning (../10-greedy/ থাকলে, নাহলে folder 03), 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) — সব দরকারি character cover করা shortest window।
  • Longest Substring Without Repeating Characters (LeetCode 3)।
  • Inherits from: sliding window (../02-arrays-and-strings/), frequency hashmap (../05-hashing/)।

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" at leetcode.com (premium)।
  • Merge k Sorted Lists (LeetCode 23) — সেই একই "always need the smallest frontier" instinct, end time-এর জায়গায় list head।
  • Heap ছাড়া warm-up: Merge Intervals (LeetCode 56)।
  • Inherits from: heaps (../08-heaps-and-priority-queues/), sorting আর sweep thinking (../03-searching-and-sorting/)।

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) — canonical দেয়াল-আর-পানির আকৃতি (two pointers দিয়েও হয়; দুটোই জানাটাই flex)।
  • Daily Temperatures (LeetCode 739) — খাঁটি next-greater drill।
  • Inherits from: stacks (../04-linked-lists/ বা এই repo-র stacks-and-queues folder), array scanning (../02-arrays-and-strings/)।

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) — grid-টা একটা DAG, কারণ move-এ value strictly বাড়ে।
  • একটা explicit dependency graph-এ path গোনা বা longest path — CSES "Longest Flight Route" / "Game Routes" at cses.fi/problemset।
  • Inherits from: graphs + topological sort (../09-graphs/topological-sort.md), DP-র state thinking (../12-dynamic-programming/)।

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) — নামটাই এর।
  • Reverse Pairs (LeetCode 493) — একই engine, queried range-এ একটা মোচড়।
  • Inherits from: Fenwick/segment trees (../11-segment-tree-and-fenwick-tree/), compression-এর জন্য sorting (../03-searching-and-sorting/)।

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)।
  • ≤ 16-টা item-কে k-টা সমান দলে ভাগ করা — LeetCode "Partition to K Equal Sum Subsets" at leetcode.com।
  • Inherits from: DP (../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।
  • দুই ভাগে ভাঙা closest subset sum — LeetCode "Partition Array Into Two Arrays to Minimize Sum Difference" at leetcode.com।
  • Inherits from: math level 11-এর subset enumeration আর meet-in-the-middle idea (../01-math-based-programming-fundamentals/), binary search (../03-searching-and-sorting/)।

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?"

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" at leetcode.com।)

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-এর প্রতিটা problem-এর জন্য, statement পড়ার আগে শুধু title আর constraint থেকে তোমার combo-আন্দাজটা লেখো। Hit rate track করো; ~70%-এর উপরে মানে dictionary-টা বসে গেছে।
  3. আন্দাজ miss করলে problem note-এ এক লাইন লেখো: "আমি X আন্দাজ করেছিলাম কারণ ; আসলে Y ছিল কারণ ।" Miss-গুলো hit-এর চেয়ে দ্রুত signal শেখায়।
  4. সপ্তাহে একবার Codeforces problem set বা CSES খোলো, পাঁচটা random statement পড়ো, আর ONLY classify করো — solve নয়। Solve করার চাপ ছাড়া classification-ই সবচেয়ে সস্তা recognition training।
  5. যেকোনো জায়গায় যেকোনো hard problem-এ আটকালে, হতাশ হওয়ার আগে cheat sheet-টা উপর থেকে নিচে checklist হিসেবে চালাও। "আটটার একটাও মেলে না" বিরল — আর সত্যি হলে সাধারণত মানে problem-টা ভয়ের পোশাক-পরা একটা single-tool problem।