Minimum inversion count in subarrays of fixed length

Array Segment Tree Sliding Window

42.5% acceptance

Feb 25, 2026

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

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_inversion_count(nums: Vec<i32>, k: i32) -> i64 {
    let n = nums.len();
    let k = k as usize;
    if k <= 1 { return 0; }

    // Coordinate compression: map values to ranks 1..=m
    let mut sorted = nums.clone();
    sorted.sort_unstable();
    sorted.dedup();
    let m = sorted.len();
    let compress = |x: i32| -> usize {
      sorted.partition_point(|&v| v < x) + 1
    };

    // Fenwick Tree (BIT), 1-indexed, size m
    let mut bit = vec![0i64; m + 2];

    macro_rules! bit_update {
      ($i:expr, $d:expr) => {{
        let mut i = $i;
        while i <= m { bit[i] += $d; i += i & i.wrapping_neg(); }
      }}
    }
    macro_rules! bit_query {
      ($i:expr) => {{
        let mut i = $i; let mut s = 0i64;
        while i > 0 { s += bit[i]; i -= i & i.wrapping_neg(); }
        s
      }}
    }

    // Count inversions in first window [0..k) by inserting left to right
    let mut inv = 0i64;
    for i in 0..k {
      let ci = compress(nums[i]);
      // Elements already inserted that are greater than nums[i]
      inv += i as i64 - bit_query!(ci);
      bit_update!(ci, 1);
    }

    let mut ans = inv;

    // Slide window: remove nums[l], add nums[l+k]
    for l in 0..(n - k) {
      let cl = compress(nums[l]);
      let cr = compress(nums[l + k]);

      // Remove nums[l]: lose inversions with elements smaller than it in the window
      if cl > 1 {
        inv -= bit_query!(cl - 1);
      }
      bit_update!(cl, -1);

      // Add nums[l+k]: gain inversions with elements greater than it in the window
      inv += (k as i64 - 1) - bit_query!(cr);
      bit_update!(cr, 1);

      ans = ans.min(inv);
    }

    ans
  }
}