Count inversions in an array efficiently
Overview
This question evaluates understanding of inversion counting and algorithmic design, specifically comparing naive O(n^2) approaches with O(n log n) divide-and-conquer strategies while requiring analysis of time and space complexity.
Akuna Capital
Sep 6, 2025, 12:00 AM
Software Engineer
Take-home Project
Coding & Algorithms
0
0
Given the array [5, 7, 9, 2, 3, 12, 8, 4], compute the number of inversion pairs (i, j) where i < j and arr[i] > arr[j]. Describe both a naive O(n^ 2) approach and an O(n log n) divide-and-conquer method, and analyze their complexities.