beingsde
Sign In
Back to all DSA patterns
Divide & Conquer•Pattern: Merge Sort / Divide & Conquer•Medium

Count inversions in array

Problem Intuition & Objective

Count pairs (i, j) where i < j but arr[i] > arr[j] using modified merge sort.

Time ComplexityO(n log n)
Optimal
Space ComplexityO(n)
Memory Bounds
Optimal Algorithmic Approach

Modified merge sort: count inversions during merge phase.

Core Invariants & Edge Cases

  • During the merge step, when a right-half element is placed before left-half elements, all remaining left-half elements form inversions
  • Count = mid - left_pointer for each such placement
  • Piggybacks on merge sort for O(n log n)
Previous ProblemPow(x, n) — fast exponentiationNext Problem Generate parentheses — all valid combinations of n pairs

System Design & Architecture Roadmap

Coding interviews are only 50% of the bar. Master High-Level Design, distributed systems, and Object-Oriented LLD.

60+ HLD QuestionsSharding, caching, and real-time distributed systems.27 LLD BlueprintsObject-oriented design patterns with class diagrams.SDE Quick ReferenceLatency numbers and database selection matrix.