Watch 2 video solutions for Minimum Inversion Count in Subarrays of Fixed Length, a hard level problem involving Array, Segment Tree, Sliding Window. This walkthrough by Programming Live with Larry has 162 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Example 1:
Input: nums = [3,1,2,5,4], k = 3
Output: 0
Explanation:
We consider all subarrays of length k = 3 (indices below are relative to each subarray):
[3, 1, 2] has 2 inversions: (0, 1) and (0, 2).[1, 2, 5] has 0 inversions.[2, 5, 4] has 1 inversion: (1, 2).The minimum inversion count among all subarrays of length 3 is 0, achieved by subarray [1, 2, 5].
Example 2:
Input: nums = [5,3,2,1], k = 4
Output: 6
Explanation:
There is only one subarray of length k = 4: [5, 3, 2, 1].
Within this subarray, the inversions are: (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), and (2, 3).
Total inversions is 6, so the minimum inversion count is 6.
Example 3:
Input: nums = [2,1], k = 1
Output: 0
Explanation:
All subarrays of length k = 1 contain only one element, so no inversions are possible.
The minimum inversion count is therefore 0.
Constraints:
1 <= n == nums.length <= 1051 <= nums[i] <= 1091 <= k <= nProblem Overview: Given an array and a fixed window size k, examine every contiguous subarray of length k and compute its inversion count (pairs i < j where arr[i] > arr[j]). The goal is to return the minimum inversion count among all such windows.
Approach 1: Brute Force Window Enumeration (O(n * k log k) time, O(k) space)
Iterate through every subarray of size k. For each window, compute the inversion count independently. A simple method copies the window, then counts inversions using merge sort or nested loops. Merge-sort-based counting takes O(k log k) per window, while naive pair comparison takes O(k²). Since there are n - k + 1 windows, total time becomes O(n * k log k). This approach is straightforward but recomputes inversion counts from scratch for overlapping windows, which wastes work.
Approach 2: Sliding Window + Fenwick Tree / Segment Tree (O(n log n) time, O(n) space)
The key observation: adjacent windows differ by exactly one removed element and one inserted element. Instead of recomputing the entire inversion count, update it incrementally. Maintain element frequencies in a Fenwick Tree (or a segment tree) after applying coordinate compression to the array values.
First build the inversion count for the initial window of size k. For each element inserted, query how many existing elements are greater than it to determine new inversions. Then slide the window. When removing the leftmost element x, subtract the inversions it formed with elements to its right by querying how many values in the structure are smaller than x. After removing it from the tree, insert the new element entering the window and add the inversions it forms with current elements (values greater than it). Each update requires O(log n) operations.
This incremental maintenance keeps the inversion count updated while scanning the array once. The technique combines a sliding window with efficient order statistics queries on a dynamic frequency structure. Total complexity becomes O(n log n), which handles large arrays comfortably.
Recommended for interviews: The sliding window with Fenwick Tree or Segment Tree is the expected solution. Interviewers often look for the insight that overlapping windows allow incremental updates. Showing the brute-force idea demonstrates understanding of inversion counting, but optimizing it with a logarithmic data structure shows strong algorithmic skill.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Merge Sort Inversion Count | O(n * k log k) | O(k) | Small arrays or when demonstrating the classic inversion counting technique |
| Sliding Window + Fenwick Tree | O(n log n) | O(n) | General case with large inputs where windows overlap and updates must be efficient |
| Sliding Window + Segment Tree | O(n log n) | O(n) | Alternative to Fenwick Tree when range queries and updates need more flexibility |