Inversions with a BIT
Count out-of-order pairs efficiently.
Inversions with a BIT is a free Coding Interview Prep lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
What Is an Inversion?
An inversion is a pair i < j where a[i] > a[j]. It is a single out-of-order pair, and counting them measures how unsorted an array is.
Why Inversions Matter
Inversion count equals the number of swaps a bubble sort would make. Contest problems hide it inside ranking and disorder questions.
The Naive Count Is Too Slow
Checking every pair is O(n^2). For n around 100000 that is ten billion checks, far past the time limit. We need something smarter. 🐢
The BIT Idea
Sweep left to right and ask: how many earlier elements are greater than the current one? A Fenwick tree answers that as we go.
Count by Frequency
The BIT stores a frequency table over values. update(v, 1) records that value v has appeared so far in our sweep.
update(v, 1)Greater Means Suffix
Earlier values greater than v are the seen count minus those up to v. That is i minus query(v) at the i-th element.
inv += i - query(v)Coordinate Compression
If values are large or negative, map them to ranks 1..n first. This compression keeps the BIT small without changing any order.
rank = {v: i for i, v in enumerate(sorted(set(a)), 1)}The Full Sweep
Loop the array, add each greater-count to the total, then insert the current value. The running total is your inversion count.
for i, v in enumerate(a):
inv += i - query(rank[v])
update(rank[v], 1)It Runs in n log n
Each element triggers one query and one update, both O(log n). The whole count finishes in O(n log n) time. 🚀
Merge Sort Is the Cousin
Merge sort also counts inversions in O(n log n) during its merge step. The BIT version is often shorter to write under pressure.
Watch the Count Overflow
Inversions can reach about n squared over two, which is huge. Python integers are unbounded, but in other languages you would need a 64-bit type.
Quick Check
Test your grasp of the sweep cost.
Recap: Counting Disorder
You counted inversions in O(n log n) by sweeping left to right and asking a BIT how many bigger values came before. Compress values when needed. ✅
Frequently asked questions
Is the “Inversions with a BIT” lesson free?
Yes — the full text of “Inversions with a BIT” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Inversions with a BIT”?
Count out-of-order pairs efficiently. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Inversions with a BIT” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.