029 — Count of Smaller Numbers After Self

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

• Original source: Classic capstone interview problem (order statistics via BIT)
• Platform: LeetCode — https://leetcode.com/problems/count-of-smaller-numbers-after-self/
• 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)।

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

তোমাকে একটা integer array nums দেওয়া আছে। প্রতিটা element-এর জন্য বলতে হবে — তার ডান দিকে তার চেয়ে কঠোরভাবে ছোট কতগুলো element আছে। ফলাফল একটা array, যেখানে counts[i] = nums[i]-এর ডানে কতগুলো element nums[i]-এর চেয়ে ছোট।

উদাহরণ

nums   : [5, 2, 6, 1]
counts : [2, 1, 1, 0]

5-র ডানে ছোট: 2, 1      -> 2
2-র ডানে ছোট: 1         -> 1
6-র ডানে ছোট: 1         -> 1
1-র ডানে ছোট: কিছু না   -> 0

Input ও output

উদাহরণ

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]   (কমতি)

চেনা উদাহরণে বোঝা

ভাবো তুমি একটা মিছিলের একদম পেছনে দাঁড়িয়ে, লোকজন এক এক করে তোমার পাশ দিয়ে সামনে যাচ্ছে — তুমি প্রত্যেকের উচ্চতা একটা খাতায় টালি দিয়ে রাখছ ("আমার চেয়ে বেঁটে কজন এসেছে এ পর্যন্ত")।

মিছিলকে উল্টো দিক থেকে (পেছন থেকে সামনে) দেখলে, যেকোনো মুহূর্তে তোমার খাতায় ঠিক ওই লোকগুলো টালি হয়ে আছে যারা মূল সারিতে এর ডানে ছিল। তাই "আমার চেয়ে বেঁটে কজন আমার ডানে" — খাতার টালি গুনলেই পাওয়া যায়, পুরো সারি প্রতিবার গোনার দরকার নেই।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

এই 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)।

ভেতরের যুক্তি

লুকানো 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)।

কী দিয়ে তথ্য রাখব

• একটা Fenwick tree (BIT) যেখানে index = compressed value rank, tree[r] ওই rank-এর value কতবার দেখা গেছে তার count জমায়।
• distinct value-দের একটা sorted list (rank ↔ value mapping, binary search-এর জন্য)।
• ফলাফলের counts array।

এটি কেন উপযুক্ত

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 লাগে না।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

প্রথম সরল চিন্তা: প্রতিটা i-র জন্য তার ডানের (j > i) সব element দেখে গোনো কতগুলো nums[j] < nums[i]।

উদাহরণ

for i in range(n):
    c = 0
    for j in range(i + 1, n):
        if nums[j] < nums[i]:
            c += 1
    counts[i] = c

কোথায় বেশি কাজ হচ্ছে

দুটো nested loop — প্রতিটা i-র জন্য ডানের সব element scan — মোট O(n²)। n বড় (10^5) হলে প্রায় 10^10 operation, time limit exceeded। কারণ একই "কতগুলো ছোট" তথ্য বারবার নতুন করে গোনা হচ্ছে — BIT-as-frequency-table (11) সেটাকে O(log n)-এ নামায়।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: array-টা ডান থেকে বাঁয়ে process করলে, প্রতিটা element-এর সময় BIT-এ ঠিক তার ডানের element-গুলোই থাকে — তাই "ডানে কতগুলো ছোট" স্রেফ একটা prefix count। BIT-এর index মানে value-র rank, position নয়; এই value-উপর-frequency দৃষ্টিভঙ্গিই O(n²)-কে O(n log n)-এ নামায়।

আরও কম কাজে সমাধান

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 ছোট চাই)।

ভাবনার পরিবর্তন

মোচড়: "প্রতিটা element-এর জন্য ডানে scan করব" ভাবার বদলে ভাবো "ডান থেকে বাঁ হাঁটব, আর প্রতিটা value-কে frequency table-এ ফেলব — তখন 'ডানে কতগুলো ছোট' স্রেফ একটা prefix count।" O(n²) double-loop একটা O(n log n) BIT-sweep-এ গুটিয়ে যায়।

ছবিতে বোঝা

[5, 2, 6, 1] — distinct sort করে rank, তারপর ডান-থেকে-বাঁ scan:

উদাহরণ

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-এ ধাপে ধাপে

[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]। ✓

কোড ও ব্যাখ্যা

Python

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!")

কোডের প্রতিটি অংশ

• 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 মিলিয়ে দেখা

[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!।

খরচ ও সাধারণ ভুল

সময়

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)।

অতিরিক্ত জায়গা

O(n) — BIT array (distinct-value-সংখ্যার সমান), rank map, আর counts array।

যে ভুলগুলো এড়াতে হবে

• 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।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি: BIT-as-frequency-table + order statistics (11 Fenwick, ../../11-segment-tree-and-fenwick-tree/fenwick-tree.md section 9; ওই folder-এর #13/#16-এও একই reflex) + coordinate compression (sorting) + ডান-থেকে-বাঁ array scan (02 arrays)। তিনটা cold-এ জানা থাকলে এই হার্ড সমাধান গড়ে ওঠে।

পরের অনুশীলন

• Reverse Pairs (a[i] > 2·a[j], BIT/merge counting) — https://leetcode.com/problems/reverse-pairs/
• Count of Range Sum (prefix sum + BIT/merge) — https://leetcode.com/problems/count-of-range-sum/
• Create Sorted Array through Instructions (BIT frequency) — https://leetcode.com/problems/create-sorted-array-through-instructions/

কৌশলটি মনে রাখুন

BIT order statistics + coordinate compression: array ডান-থেকে-বাঁ scan করে প্রতিটা value-কে rank-compressed BIT-এ frequency হিসেবে রাখা, আর "ডানে কতগুলো ছোট" = prefix_count(rank - 1)। index মানে value, position নয় — Fenwick + sorting + arrays-এর canonical counting মেলবন্ধন।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "প্রতিটা element-এর ডানে/বাঁয়ে কতগুলো ছোট/বড়" দেখলেই BIT-over-values + right-to-left scan মনে করবে। distinct value compress করো; ডান থেকে বাঁ হাঁটো; counts[i] = prefix_count(rank-1) তারপর add(rank, 1)। rank-1 কঠোরভাবে-ছোট নিশ্চিত করে। O(n²)-কে O(n log n)-এ নামানোর সবচেয়ে পরিষ্কার counting trick।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।