Count inversions in a permutation

Q: Count inversions in a permutation

This question evaluates understanding of inversion counting in permutations, testing algorithmic problem-solving, complexity analysis, and data-structure reasoning about pairwise order relations.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Problem

Given an array a of length n that is a permutation of distinct integers (e.g., 1..n), define an inversion as a pair of indices (i, j) such that:

0 ≤ i < j < n , and
a[i] > a[j] .

Task

Write a function that returns the number of inversions in the array.

Input/Output

Input: an integer array a with all distinct values
Output: a single integer = the number of inversions

Notes

Any time complexity is acceptable (e.g., an O(n^2) approach is fine), but you may also discuss faster approaches if you know them.

Count inversions in a permutation

Overview

Problem

Task

Input/Output

Notes

Comments (0)