FastPrep
Problem · Array

Count Array Inversions

Learn this problem
● MediumTCTCSFULLTIMEOA

Problem statement

Given an integer array nums, return the number of inversions in it.

An inversion is a pair of indices (i, j) such that i < j and nums[i] > nums[j]. Equal values do not form an inversion.

Function

countInversions(nums: int[]) → long

Examples

Example 1

nums = [2,4,1,3,5]return = 3

The inverted pairs are (2,1), (4,1), and (4,3).

Example 2

nums = [5,4,3,2,1]return = 10

Every pair is inverted in a length-five descending array.

Constraints

  • 1 <= nums.length <= 200000
  • -2^31 <= nums[i] <= 2^31 - 1
  • The answer fits in a signed 64-bit integer.

More TCS problems

drafts saved locally
public long countInversions(int[] nums) {
    // Write your code here.
}
nums[2,4,1,3,5]
expected3
checking account