029 — Count of Smaller Numbers After Self

Source

• 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), 03 sorting (distinct value sort করে rank), আর 02 arrays (ডান-থেকে-বাঁ array traversal)। তিন tool মিলে O(n log n)।

1. Problem in simple words

তোমাকে একটা 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

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)।
• 03 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 (03 sorting) BIT-কে ছোট ও দ্রুত রাখে। ডান-থেকে-বাঁ scan (02 arrays) নিশ্চিত করে query-র সময় BIT-এ শুধু সঠিক (ডানের) element-গুলোই আছে — তাই extra bookkeeping লাগে না।

6. Real-life analogy

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

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

7. Visual explanation

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

8. Example input and 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]   (কমতি)

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতিটা 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

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-এ গুটিয়ে যায়।

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

15. Python solution

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, 03 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-এর উত্তর যাচাই করতে।

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

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।

21. Which basic problem this inherits from

ভিত্তি: 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 (03 sorting) + ডান-থেকে-বাঁ array scan (02 arrays)। তিনটা cold-এ জানা থাকলে এই হার্ড সমাধান গড়ে ওঠে।

22. Similar harder problems

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

23. Pattern learned

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

24. Final summary

ভবিষ্যতের আমাকে: "প্রতিটা 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।