#3768
Minimum Inversion Count in Subarrays of Fixed Length
hard · 42.5% accepted · 48 likes · top 24%
array · segment tree · sliding window
Description
You are given an integer array nums of length n and an integer k.
An inversion is a pair of indices (i, j) from nums such that i < j and nums[i] > nums[j].
The inversion count of a subarray is the number of inversions within it.
Return the minimum inversion count among all subarrays of nums with length k.
Solution