How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Akuna Capital.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Akuna Capital during technical interviews.

Count inversions in an array efficiently | Akuna Capital Coding Question

Count inversions in an array efficiently

Company: Akuna Capital

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

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.

Quick Answer: 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.

Given an integer array `arr`, count the number of inversion pairs `(i, j)` such that `i < j` and `arr[i] > arr[j]`. An inversion measures how far the array is from being sorted in ascending order: a sorted array has 0 inversions, and a strictly descending array of length n has the maximum n*(n-1)/2 inversions. For example, given `[5, 7, 9, 2, 3, 12, 8, 4]`, the answer is `13`. The naive approach checks every pair in O(n^2) time. The efficient approach augments merge sort: while merging two sorted halves, every time an element from the right half is placed before remaining elements of the left half, all those remaining left elements form inversions with it, giving O(n log n) time. Return the total number of inversion pairs as an integer.

Constraints

0 <= len(arr) <= 10^5
-10^9 <= arr[i] <= 10^9
Array elements may contain duplicates and negative numbers
Equal elements (arr[i] == arr[j]) do NOT form an inversion

Examples

Input: [5, 7, 9, 2, 3, 12, 8, 4]

Expected Output: 13

Explanation: The 13 inversion pairs include (5,2),(5,3),(5,4),(7,2),(7,3),(7,4),(9,2),(9,3),(9,8),(9,4),(12,8),(12,4),(8,4).

Input: []

Expected Output: 0

Explanation: An empty array has no pairs, so 0 inversions.

Input: [1]

Expected Output: 0

Explanation: A single element has no pair to compare against.

Input: [1, 2, 3, 4, 5]

Expected Output: 0

Explanation: A fully ascending array has no inversions.

Input: [5, 4, 3, 2, 1]

Expected Output: 10

Explanation: A strictly descending array of length 5 has the maximum 5*4/2 = 10 inversions.

Input: [2, 2, 2, 2]

Expected Output: 0

Explanation: Equal elements are not inversions (the condition is strict arr[i] > arr[j]).

Input: [-1, -3, 5, -2, 0]

Expected Output: 4

Explanation: Inversions: (-1,-3),(-1,-2),(5,-2),(5,0).

Hints

The naive solution is a double loop over all pairs (i, j) with i < j, counting when arr[i] > arr[j]. This is O(n^2) and a correct baseline.
To get O(n log n), modify merge sort. The total inversion count equals inversions within the left half, plus inversions within the right half, plus cross-half inversions discovered during the merge.
During the merge of two sorted halves, when you pick an element from the RIGHT half (because it is smaller than the current LEFT element), every remaining element in the left half is greater than it — add (number of remaining left elements) to the count.

Quick 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.