Problem link ও উৎস
- **Original source:** Classic capstone interview problem (order statistics via BIT)
- **Platform:** LeetCode —
- **Topic:** Fenwick tree + sorting + arrays
- **Difficulty:** Hard
- **Pattern:** BIT order statistics + coordinate compression (value-দের উপর frequency count)
- **Basic idea inherited from:** এটা একটা cross-topic capstone — এখানে মেশে **11 Fenwick** (value-দের উপর frequency BIT), **sorting** (distinct value sort করে rank), আর **02 arrays** (ডান-থেকে-বাঁ array traversal)। তিন tool মিলে O(n log n)।
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা integer array `nums` দেওয়া আছে। প্রতিটা element-এর জন্য বলতে হবে — তার **ডান দিকে** তার চেয়ে **কঠোরভাবে ছোট** কতগুলো element আছে। ফলাফল একটা array, যেখানে `counts[i]` = `nums[i]`-এর ডানে কতগুলো element `nums[i]`-এর চেয়ে ছোট।
```text
nums : [5, 2, 6, 1]
counts : [2, 1, 1, 0]
5-র ডানে ছোট: 2, 1 -> 2
2-র ডানে ছোট: 1 -> 1
6-র ডানে ছোট: 1 -> 1
1-র ডানে ছোট: কিছু না -> 0
```
### Input ও output {#8-example-input-and-output}
```text
Input : [5, 2, 6, 1] -> Output: [2, 1, 1, 0]
Input : [-1] -> Output: [0]
Input : [-1, -1] -> Output: [0, 0] (সমান, strictly ছোট নয়)
Input : [1, 2, 3, 4] -> Output: [0, 0, 0, 0] (বাড়তি, ডানে ছোট নেই)
Input : [4, 3, 2, 1] -> Output: [3, 2, 1, 0] (কমতি)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তুমি একটা মিছিলের একদম পেছনে দাঁড়িয়ে, লোকজন এক এক করে তোমার পাশ দিয়ে সামনে যাচ্ছে — তুমি প্রত্যেকের উচ্চতা একটা খাতায় টালি দিয়ে রাখছ ("আমার চেয়ে বেঁটে কজন এসেছে এ পর্যন্ত")।
মিছিলকে উল্টো দিক থেকে (পেছন থেকে সামনে) দেখলে, যেকোনো মুহূর্তে তোমার খাতায় ঠিক ওই লোকগুলো টালি হয়ে আছে যারা মূল সারিতে এর *ডানে* ছিল। তাই "আমার চেয়ে বেঁটে কজন আমার ডানে" — খাতার টালি গুনলেই পাওয়া যায়, পুরো সারি প্রতিবার গোনার দরকার নেই।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এই problem তিনটা আগের ধারণা জোড়া দেয়:
- **11 Fenwick** থেকে: একটা BIT-কে *value-দের উপর frequency table* হিসেবে দেখা — `add(v, +1)` মানে "value v দেখলাম", `prefix_count(v-1)` মানে "এ পর্যন্ত দেখা কতগুলো value `< v`" (folder 11-এর `fenwick-tree.md` section 9-এর core)।
- **sorting** থেকে: value 10^9 পর্যন্ত হতে পারে, তাই distinct value sort করে **rank/coordinate compression** — BIT ছোট রাখতে।
- **02 arrays** থেকে: array-টা **ডান থেকে বাঁয়ে** scan, যাতে প্রতিটা element process করার সময় শুধু তার ডানের element-গুলোই BIT-এ আছে।
একা Fenwick দেয় fast count; একা sorting দেয় compact index; ডান-থেকে-বাঁ scan দেয় "শুধু ডানের" guarantee। তিন মিলে O(n log n)।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা **"ডান থেকে বাঁ" insertion order**: যদি আমরা array-টা শেষ থেকে শুরুর দিকে process করি আর প্রতিটা দেখা value BIT-এ যোগ করি, তবে যখন আমরা `nums[i]`-এ পৌঁছাই, BIT-এ ঠিক তার ডানের element-গুলোই আছে।
তখন "`nums[i]`-এর চেয়ে কতগুলো ছোট" = এ পর্যন্ত যোগ করা value-গুলোর মধ্যে কতগুলো `< nums[i]` = `prefix_count(rank(nums[i]) - 1)`। এটাই order-statistics query, BIT-এ O(log n)।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
- একটা **Fenwick tree (BIT)** যেখানে index = compressed value rank, `tree[r]` ওই rank-এর value কতবার দেখা গেছে তার count জমায়।
- distinct value-দের একটা **sorted list** (rank ↔ value mapping, binary search-এর জন্য)।
- ফলাফলের **counts array**।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Brute O(n²) প্রতিটা element-এর জন্য তার ডানের সব element গোনে। আমরা চাই "কতগুলো ছোট" দ্রুত জানতে — যা BIT-as-frequency-table (11) ঠিক দেয়: `prefix_count` এক query-তেই "কতগুলো ≤ v" বলে।
value বিশাল হলেও distinct value-র সংখ্যা ≤ n, তাই coordinate compression (sorting) BIT-কে ছোট ও দ্রুত রাখে। ডান-থেকে-বাঁ scan (02 arrays) নিশ্চিত করে query-র সময় BIT-এ শুধু সঠিক (ডানের) element-গুলোই আছে — তাই extra bookkeeping লাগে না।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা `i`-র জন্য তার ডানের (`j > i`) সব element দেখে গোনো কতগুলো `nums[j] < nums[i]`।
```text
for i in range(n):
c = 0
for j in range(i + 1, n):
if nums[j] < nums[i]:
c += 1
counts[i] = c
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
দুটো nested loop — প্রতিটা `i`-র জন্য ডানের সব element scan — মোট **O(n²)**। `n` বড় (10^5) হলে প্রায় 10^10 operation, time limit exceeded। কারণ একই "কতগুলো ছোট" তথ্য বারবার নতুন করে গোনা হচ্ছে — BIT-as-frequency-table (11) সেটাকে O(log n)-এ নামায়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **array-টা ডান থেকে বাঁয়ে process করলে, প্রতিটা element-এর সময় BIT-এ ঠিক তার ডানের element-গুলোই থাকে** — তাই "ডানে কতগুলো ছোট" স্রেফ একটা prefix count। BIT-এর index মানে value-র rank, position নয়; এই value-উপর-frequency দৃষ্টিভঙ্গিই O(n²)-কে O(n log n)-এ নামায়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
distinct value sort করে rank দাও (coordinate compression)। একটা খালি BIT নাও। array-টা **ডান থেকে বাঁ** scan করো:
- `nums[i]`-এর জন্য: `counts[i] = prefix_count(rank(nums[i]) - 1)` — এ পর্যন্ত দেখা (অর্থাৎ ডানের) কতগুলো value কঠোরভাবে ছোট।
- তারপর `add(rank(nums[i]), +1)` — এই value-কে "দেখা" হিসেবে BIT-এ যোগ করো।
`rank - 1` ব্যবহার নিশ্চিত করে সমান value গোনা হয় না (strictly ছোট চাই)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "প্রতিটা element-এর জন্য ডানে scan করব" ভাবার বদলে ভাবো "ডান থেকে বাঁ হাঁটব, আর প্রতিটা value-কে frequency table-এ ফেলব — তখন 'ডানে কতগুলো ছোট' স্রেফ একটা prefix count।" O(n²) double-loop একটা O(n log n) BIT-sweep-এ গুটিয়ে যায়।
### ছবিতে বোঝা {#7-visual-explanation}
`[5, 2, 6, 1]` — distinct sort করে rank, তারপর ডান-থেকে-বাঁ scan:
```text
distinct sorted: 1 2 5 6
rank (1-indexed): 1 2 3 4
ডান থেকে বাঁ process; BIT-এ frequency জমে:
i=3, nums=1 (rank 1): ডানে কিছু নেই -> count = prefix_count(0) = 0; add(1)
i=2, nums=6 (rank 4): prefix_count(3) = এ পর্যন্ত rank<=3 কতগুলো = 1 (শুধু 1); add(4)
i=1, nums=2 (rank 2): prefix_count(1) = rank<=1 কতগুলো = 1 (শুধু 1); add(2)
i=0, nums=5 (rank 3): prefix_count(2) = rank<=2 কতগুলো = 2 (1 আর 2); add(3)
counts (ক্রমে): [2, 1, 1, 0]
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`[5, 2, 6, 1]`, rank `{1:1, 2:2, 5:3, 6:4}`, ডান থেকে বাঁ:
1. `i=3`, `nums=1` (rank 1): `counts[3] = prefix_count(0) = 0`; `add(1)`। BIT: rank1→1।
2. `i=2`, `nums=6` (rank 4): `counts[2] = prefix_count(3) = 1` (শুধু rank1=1টা); `add(4)`। BIT: rank1,rank4।
3. `i=1`, `nums=2` (rank 2): `counts[1] = prefix_count(1) = 1` (rank1=1টা); `add(2)`। BIT: rank1,2,4।
4. `i=0`, `nums=5` (rank 3): `counts[0] = prefix_count(2) = 2` (rank1,rank2); `add(3)`।
5. `counts = [2, 1, 1, 0]`। ✓
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
import bisect
class Fenwick:
"""value-দের উপর FREQUENCY table (folder 11-এর fenwick-tree.md section 9)।
index = compressed value rank (1-indexed)। add(r, +1): rank r-এ একটা গোনা;
prefix_count(r): rank <= r মোট কতগুলো দেখা গেছে।"""
def __init__(self, size):
self.n = size
self.tree = [0] * (size + 1) # 1-indexed
def add(self, i, delta):
while i <= self.n:
self.tree[i] += delta
i += i & (-i) # পরের block-এ লাফ
def prefix_count(self, i): # rank 1..i মোট count
s = 0
while i > 0:
s += self.tree[i]
i -= i & (-i) # last set bit ঝাড়ো
return s
def count_smaller(nums):
"""BIT order statistics (11) + sorting-based compression (03) + array
right-to-left scan (02)। প্রতিটা element-এর ডানে কতগুলো ছোট। O(n log n)।"""
if not nums:
return []
comp = sorted(set(nums)) # distinct value sort -> rank
rank = {v: i + 1 for i, v in enumerate(comp)} # 1-indexed rank
bit = Fenwick(len(comp))
counts = [0] * len(nums)
for i in range(len(nums) - 1, -1, -1): # ডান থেকে বাঁ
r = rank[nums[i]]
counts[i] = bit.prefix_count(r - 1) # কঠোরভাবে ছোট (r-1)
bit.add(r, 1) # এই value-কে 'দেখা' হিসেবে যোগ
return counts
def brute(nums):
# obviously-correct reference: O(n^2) double loop
n = len(nums)
out = [0] * n
for i in range(n):
out[i] = sum(1 for j in range(i + 1, n) if nums[j] < nums[i])
return out
# ---- tests ----
assert count_smaller([5, 2, 6, 1]) == [2, 1, 1, 0]
assert count_smaller([-1]) == [0]
assert count_smaller([-1, -1]) == [0, 0] # সমান -> strictly ছোট নয়
assert count_smaller([]) == []
assert count_smaller([1, 2, 3, 4]) == [0, 0, 0, 0] # বাড়তি
assert count_smaller([4, 3, 2, 1]) == [3, 2, 1, 0] # কমতি
assert count_smaller([2, 2, 2]) == [0, 0, 0] # সব সমান
# বড় ও negative + duplicate মিশ্র
assert count_smaller([10, -5, 10, -5, 3]) == brute([10, -5, 10, -5, 3])
# random fuzz: BIT vs brute
import random
random.seed(29)
for _ in range(1000):
n = random.randint(0, 12)
arr = [random.randint(-10, 10) for _ in range(n)]
assert count_smaller(arr) == brute(arr), arr
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `Fenwick.add / prefix_count` — standard BIT: `add` lowbit যোগ করে এগোয়, `prefix_count` lowbit বিয়োগ করে prefix count জমায়।
- `comp` / `rank` — distinct value sort করে 1-indexed rank (coordinate compression, sorting)।
- `for i in range(len(nums)-1, -1, -1)` — ডান থেকে বাঁ scan; তাই query-র সময় BIT-এ শুধু ডানের element।
- `bit.prefix_count(r - 1)` — `nums[i]`-এর চেয়ে কঠোরভাবে ছোট কতগুলো দেখা গেছে (`r-1` সমান value বাদ দেয়)।
- `bit.add(r, 1)` — current value-কে frequency table-এ যোগ।
- `brute` — O(n²) double-loop reference, BIT-এর উত্তর যাচাই করতে।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[5,2,6,1]` ডান-থেকে-বাঁ process হয়: 1→0, 6→1, 2→1, 5→2, ফলে `[2,1,1,0]`। একক/সমান/খালি/বাড়তি/কমতি/সব-সমান সব edge সঠিক; negative+duplicate মিশ্র brute-এর সাথে মেলে। শেষে 1000 random fuzz-এ BIT version O(n²) brute-এর সাথে মেলে। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n log n)** — compression-এ distinct value sort O(n log n); তারপর প্রতিটা element-এ একটা `prefix_count` + একটা `add` + একটা rank-lookup, প্রতিটা O(log n); মোট O(n log n)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — BIT array (distinct-value-সংখ্যার সমান), rank map, আর counts array।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- `prefix_count(r)` ব্যবহার করা যেখানে `prefix_count(r - 1)` দরকার — তাহলে সমান value-ও গোনা হয়, কিন্তু "কঠোরভাবে ছোট" চাই (folder 11-এর off-by-one)।
- বাঁ-থেকে-ডান scan করা — তাহলে BIT-এ ভুল (বাঁয়ের) element থাকবে; ডান-থেকে-বাঁ চাই।
- coordinate compression বাদ দেওয়া — value 10^9 হলে BIT array বানানো অসম্ভব।
- BIT-এর index-কে position ভাবা — এখানে index মানে value-র rank।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: BIT-as-frequency-table + order statistics (11 Fenwick, [../../11-segment-tree-and-fenwick-tree/fenwick-tree.md](../../11-segment-tree-and-fenwick-tree/fenwick-tree.md) section 9; ওই folder-এর #13/#16-এও একই reflex) + coordinate compression (sorting) + ডান-থেকে-বাঁ array scan (02 arrays)। তিনটা cold-এ জানা থাকলে এই হার্ড সমাধান গড়ে ওঠে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Reverse Pairs (`a[i] > 2·a[j]`, BIT/merge counting) —