3768. Minimum Inversion Count in Subarrays of Fixed Length Hard

1/**
2 * [3768] Minimum Inversion Count in Subarrays of Fixed Length
3 *
4 * You are given an integer array nums of length n and an integer k.
5 * An inversion is a pair of indices (i, j) from nums such that i < j and nums[i] > nums[j].
6 * The inversion count of a <span data-keyword="subarray-nonempty">subarray</span> is the number of inversions within it.
7 * Return the minimum inversion count among all subarrays of nums with length k.
8 *  
9 * <strong class="example">Example 1:
10 * <div class="example-block">
11 * Input: <span class="example-io">nums = [3,1,2,5,4], k = 3</span>
12 * Output: <span class="example-io">0</span>
13 * Explanation:
14 * We consider all subarrays of length k = 3 (indices below are relative to each subarray):
15 * 
16 * 	[3, 1, 2] has 2 inversions: (0, 1) and (0, 2).
17 * 	[1, 2, 5] has 0 inversions.
18 * 	[2, 5, 4] has 1 inversion: (1, 2).
19 * 
20 * The minimum inversion count among all subarrays of length 3 is 0, achieved by subarray [1, 2, 5].
21 * </div>
22 * <strong class="example">Example 2:
23 * <div class="example-block">
24 * Input: <span class="example-io">nums = [5,3,2,1], k = 4</span>
25 * Output: <span class="example-io">6</span>
26 * Explanation:
27 * There is only one subarray of length k = 4: [5, 3, 2, 1].<br />
28 * Within this subarray, the inversions are: (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), and (2, 3).<br />
29 * Total inversions is 6, so the minimum inversion count is 6.
30 * </div>
31 * <strong class="example">Example 3:
32 * <div class="example-block">
33 * Input: <span class="example-io">nums = [2,1], k = 1</span>
34 * Output: <span class="example-io">0</span>
35 * Explanation:
36 * All subarrays of length k = 1 contain only one element, so no inversions are possible.<br />
37 * The minimum inversion count is therefore 0.
38 * </div>
39 *  
40 * Constraints:
41 * 
42 * 	1 <= n == nums.length <= 10^5
43 * 	1 <= nums[i] <= 10^9
44 * 	1 <= k <= n
45 * 
46 */
47pub struct Solution {}
48
49// problem: https://leetcode.com/problems/minimum-inversion-count-in-subarrays-of-fixed-length/
50// discuss: https://leetcode.com/problems/minimum-inversion-count-in-subarrays-of-fixed-length/discuss/?currentPage=1&orderBy=most_votes&query=
51
52// submission codes start here
53
54impl Solution {
55    pub fn min_inversion_count(nums: Vec<i32>, k: i32) -> i64 {
56        
57    }
58}
59
60// submission codes end
61
62#[cfg(test)]
63mod tests {
64    use super::*;
65
66    #[test]
67    fn test_3768() {
68    }
69}
70