Skip to content

013 — Count of Smaller Numbers After Self

Source

  • Original source: LeetCode 315 — Count of Smaller Numbers After Self
  • Platform: LeetCode 315
  • Topic: segment tree and fenwick tree
  • Difficulty: Hard
  • Pattern: BIT + coordinate compression
  • Basic idea inherited from: BIT over values, sorting

1. Problem in simple words

একটা array a দেওয়া। প্রতিটা index i-র জন্য বের করো: i-র ডানদিকে কতগুলো element আছে যেগুলো a[i]-এর চেয়ে ছোট। উত্তর একটা array counts, যেখানে counts[i] = ওই সংখ্যা।

a      = [5, 2, 6, 1]
counts = [2, 1, 1, 0]

a[0]=5 -> ডানে ছোট: {2, 1}  -> 2
a[1]=2 -> ডানে ছোট: {1}     -> 1
a[2]=6 -> ডানে ছোট: {1}     -> 1
a[3]=1 -> ডানে ছোট: {}      -> 0

2. Which basic idea does this inherit from?

এটা BIT-over-values আর sorting-এর উপর দাঁড়িয়ে। #10-এ তুমি মোট inversion গুনেছিলে; এটা ঠিক তার per-element রূপ — প্রতিটা element আলাদা করে জানতে চায় তার ডানে কয়টা ছোট। BIT এখানে আবার একটা frequency table over values।

3. What is the hidden math or logic?

লুকানো logic: array ডান থেকে বাঁয়ে process করো; প্রতিটা value frequency table-এ tick দেওয়ার আগে জিজ্ঞেস করো "এ পর্যন্ত (অর্থাৎ আমার ডানে) কয়টা value আমার চেয়ে ছোট দেখা হয়েছে"। সেই answer-টাই counts[i]। ডান-থেকে-বাঁ order নিশ্চিত করে BIT-এ শুধু "ডানের" element-রাই আছে।

4. Which data structure is needed?

একটা Fenwick tree (BIT) value-দের rank-এ indexed। Value 10^4 পর্যন্ত বড় (আর negative) হতে পারে, তাই আগে coordinate compression (value → rank)।

5. Why this data structure fits

"আমার চেয়ে ছোট কয়টা ইতিমধ্যে দেখেছি" = prefix_sum(rank - 1) over a frequency table। BIT এই prefix-count আর point-increment দুটোই O(log n)-এ দেয়। n element-এ মোট O(n log n) — segment tree-ও পারত, কিন্তু BIT ছোট আর দ্রুত (../fenwick-tree.md section 8-9 দেখো)।

6. Real-life analogy

ভাবো একটা দৌড় শেষে finishers এক এক করে ভেতরে ঢুকছে, সবার গায়ে bib-number। শেষ থেকে দেখলে — প্রতিটা নতুন finisher-এর জন্য তুমি জানতে চাও "এর পরে যারা এসেছে (মানে board-এ ইতিমধ্যে আছে), তাদের কয়জনের bib এর চেয়ে ছোট"। প্রতিবার পুরো board না গুনে, bib-number অনুযায়ী একটা tally রাখো; নতুন bib-এ শুধু তার নিচের অংশটা যোগ করো।

7. Visual explanation

a = [5, 2, 6, 1]   compressed rank (1->1, 2->2, 5->3, 6->4):
                    a:     5  2  6  1
                    rank:  3  2  4  1

ডান -> বাঁ, frequency BIT-এ tick দিতে দিতে:
  a[3]=1 (rank1): prefix_sum(0) = 0  -> counts[3]=0;  add(1,1)
  a[2]=6 (rank4): prefix_sum(3) = 1  -> counts[2]=1;  add(4,1)   (শুধু 1 marked)
  a[1]=2 (rank2): prefix_sum(1) = 1  -> counts[1]=1;  add(2,1)   (শুধু 1)
  a[0]=5 (rank3): prefix_sum(2) = 2  -> counts[0]=2;  add(3,1)   (1, 2)

counts = [2, 1, 1, 0]

8. Example input and output

input:  a = [5, 2, 6, 1]
output: [2, 1, 1, 0]

input:  a = [-1]
output: [0]                 (একা, ডানে কেউ নেই)

input:  a = [-1, -1]
output: [0, 0]              (equal, strictly ছোট নয়)

9. Brute force thinking

সরল চিন্তা: প্রতি i-র জন্য ডানদিকের সব element ঘুরে ছোট গোনা।

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

নির্ভুল, এটাই reference।

10. Why brute force is slow

দুই nested loop = O(n^2)। n = 10^5 হলে 10^10 — TLE। BIT-over-values প্রতি element-এ একটা prefix-count + একটা update দিয়ে পুরোটা O(n log n)-এ নামায়।

11. Key observation

মূল observation: "ডানে কয়টা ছোট" = ডান-থেকে-বাঁ গেলে "এ পর্যন্ত দেখা value-গুলোর মধ্যে কয়টা ছোট"। Order উল্টে দিলে ভবিষ্যৎ (ডান) অতীত হয়ে যায়, আর প্রশ্নটা একটা frequency-table prefix-count-এ পরিণত হয়।

12. Optimized intuition

Coordinate compression করে value → rank। তারপর i = n-1 থেকে 0 পর্যন্ত: counts[i] = prefix_sum(rank[i] - 1) (strictly ছোট), তারপর add(rank[i], 1)। rank - 1 strict ছোট নিশ্চিত করে (equal value বাদ)। ডান-থেকে-বাঁ order মানে BIT-এ শুধু ডানের element।

13. Thinking tweak

মোচড়: per-element "ডানে কয়টা ছোট" প্রশ্নকে একটা running frequency table-এর উপর prefix-count-এ অনুবাদ করো, আর array উল্টো দিকে হাঁটো। এই reverse-sweep + BIT-frequency জোড়া #14, #16-এও ফিরে আসবে।

14. Step-by-step dry run

a = [5, 2, 6, 1], rank {1:1, 2:2, 5:3, 6:4}, BIT খালি। i = 3 → 0:

  1. i=3, a=1 (r=1): prefix_sum(0)=0 → counts[3]=0; add(1,1)।
  2. i=2, a=6 (r=4): prefix_sum(3)=1 (শুধু r1) → counts[2]=1; add(4,1)।
  3. i=1, a=2 (r=2): prefix_sum(1)=1 (শুধু r1) → counts[1]=1; add(2,1)।
  4. i=0, a=5 (r=3): prefix_sum(2)=2 (r1, r2) → counts[0]=2; add(3,1)।
  5. counts = [2, 1, 1, 0]। ✓

15. Python solution

class Fenwick:
    """1-indexed BIT, value-দের frequency table হিসেবে। index মানে VALUE-র rank,
    position নয়। add(i, 1): value-rank i একবার দেখলাম; prefix_sum(i): rank 1..i-র
    মোট গোনা। দুটোই O(log n)।"""

    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def add(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)

    def prefix_sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s


def count_smaller(a):
    n = len(a)
    if n == 0:
        return []
    # coordinate compression: value -> 1-indexed rank
    order = sorted(set(a))
    rank = {v: idx + 1 for idx, v in enumerate(order)}
    bit = Fenwick(len(order))
    counts = [0] * n
    for i in range(n - 1, -1, -1):         # ডান -> বাঁ
        r = rank[a[i]]
        counts[i] = bit.prefix_sum(r - 1)  # ডানে দেখা, আমার চেয়ে ছোট কয়টা
        bit.add(r, 1)                      # নিজেকে frequency table-এ tick
    return counts


def brute(a):
    # obviously-correct O(n^2) reference
    n = len(a)
    res = [0] * n
    for i in range(n):
        for j in range(i + 1, n):
            if a[j] < a[i]:
                res[i] += 1
    return res


# ---- tests ----
assert count_smaller([5, 2, 6, 1]) == [2, 1, 1, 0]
assert count_smaller([-1]) == [0]
assert count_smaller([-1, -1]) == [0, 0]         # equal: strictly ছোট নয়
assert count_smaller([]) == []                   # empty
assert count_smaller([1, 2, 3, 4]) == [0, 0, 0, 0]   # increasing: ডানে কিছু ছোট নেই
assert count_smaller([4, 3, 2, 1]) == [3, 2, 1, 0]   # decreasing: সব ডানেরটা ছোট

# BIT version সবসময় brute-এর সাথে একমত (duplicate, negative-সহ)
import random
for _ in range(400):
    arr = [random.randint(-6, 6) for _ in range(random.randint(0, 15))]
    assert count_smaller(arr) == brute(arr)

print("সব test pass!")

16. Line-by-line code explanation

  • Fenwick — standard BIT, এখানে value-দের frequency table; index = rank।
  • order/rank — coordinate compression, value → 1..k; বড়/negative value সামলায়।
  • count_smaller — i কমার দিকে (ডান → বাঁ) হাঁটে; prefix_sum(r-1) দেয় ডানে-দেখা ছোট value-র সংখ্যা।
  • r - 1 — strictly ছোট চাই বলে নিজের সমান value বাদ।
  • brute — O(n^2), নির্ভুল reference।

17. Output walkthrough

[5,2,6,1]-এ ডান-থেকে-বাঁ হেঁটে BIT version দেয় [2,1,1,0] (section 14)। তারপর 400-টা random array-তে — duplicate আর negative-সহ — brute-এর সাথে হুবহু মেলে। equal value ([-1,-1]) strictly ছোট নয় বলে [0,0]। শেষে print: সব test pass!।

18. Time complexity

O(n log n): প্রতি element-এ একটা prefix_sum + একটা add, প্রতিটা O(log n); compression-এর sort O(n log n)।

19. Space complexity

O(n): BIT array + rank map + output array।

20. Common mistakes

  • BIT-এ index হিসেবে position নেওয়া — index মানে VALUE-র rank, এটাই মূল মোচড়।
  • বাঁ-থেকে-ডান হাঁটা — তখন "ডানে কয়টা ছোট"-এর বদলে "বাঁয়ে কয়টা ছোট" পাও; reverse sweep জরুরি।
  • prefix_sum(r) লেখা যেখানে prefix_sum(r - 1) দরকার — equal value-ও গোনা হয়ে strict ভাঙে।
  • Coordinate compression বাদ — বড়/negative value-তে BIT index crash বা বিশাল array।

21. Which basic problem this inherits from

ভিত্তি: BIT-over-values (../fenwick-tree.md section 9) + sorting (compression)। সরাসরি বড় ভাই #10 (count inversions) — সেখানে মোট গোনা, এখানে per-element।

22. Similar harder problems

23. Pattern learned

BIT + coordinate compression: value-দের একটা frequency table BIT-এ রাখো, array reverse করে হাঁটো, প্রতি element-এ prefix_sum(rank-1) জিজ্ঞেস করো। বড় value-কে rank-এ চেপে BIT ছোট রাখা — এই reflex অনেক counting problem-এ লাগবে।

24. Final summary

ভবিষ্যতের আমাকে: "ডানে কয়টা ছোট" = array উল্টে হেঁটে compressed-value frequency BIT-এ prefix_sum(rank-1)। #10-এর মোট-গোনার per-element রূপ। index = VALUE আর reverse sweep — এই দুই কথা মনে থাকলে #14, #16 স্রেফ এই idea-র টুইস্ট।

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