Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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 summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Segment Tree · Sliding Window
[3,1,2,5,4] 3
[5,3,2,1] 4
[2,1] 1
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3768: Minimum Inversion Count in Subarrays of Fixed Length
// Auto-generated Java example from go.
class Solution {
public void exampleSolution() {
}
}
// Reference (go):
// // Accepted solution for LeetCode #3768: Minimum Inversion Count in Subarrays of Fixed Length
// package main
//
// import (
// "math"
// "slices"
// "sort"
// )
//
// // https://space.bilibili.com/206214
// type fenwick []int
//
// func (t fenwick) update(i, val int) {
// for ; i < len(t); i += i & -i {
// t[i] += val
// }
// }
//
// func (t fenwick) pre(i int) (res int) {
// for ; i > 0; i &= i - 1 {
// res += t[i]
// }
// return
// }
//
// func minInversionCount(nums []int, k int) int64 {
// // 离散化
// sorted := slices.Clone(nums)
// slices.Sort(sorted)
// sorted = slices.Compact(sorted)
// for i, x := range nums {
// nums[i] = sort.SearchInts(sorted, x) + 1
// }
//
// t := make(fenwick, len(sorted)+1)
// inv := 0
// ans := math.MaxInt
//
// for i, in := range nums {
// // 1. 入
// t.update(in, 1)
// inv += min(i+1, k) - t.pre(in) // 窗口大小 - (<=x 的元素个数) = (>x 的元素个数)
//
// left := i + 1 - k
// if left < 0 { // 尚未形成第一个窗口
// continue
// }
//
// // 2. 更新答案
// ans = min(ans, inv)
// if ans == 0 { // 已经最小了，无需再计算
// break
// }
//
// // 3. 出
// out := nums[left]
// inv -= t.pre(out - 1)
// t.update(out, -1)
// }
// return int64(ans)
// }
// Accepted solution for LeetCode #3768: Minimum Inversion Count in Subarrays of Fixed Length
package main
import (
"math"
"slices"
"sort"
)
// https://space.bilibili.com/206214
type fenwick []int
func (t fenwick) update(i, val int) {
for ; i < len(t); i += i & -i {
t[i] += val
}
}
func (t fenwick) pre(i int) (res int) {
for ; i > 0; i &= i - 1 {
res += t[i]
}
return
}
func minInversionCount(nums []int, k int) int64 {
// 离散化
sorted := slices.Clone(nums)
slices.Sort(sorted)
sorted = slices.Compact(sorted)
for i, x := range nums {
nums[i] = sort.SearchInts(sorted, x) + 1
}
t := make(fenwick, len(sorted)+1)
inv := 0
ans := math.MaxInt
for i, in := range nums {
// 1. 入
t.update(in, 1)
inv += min(i+1, k) - t.pre(in) // 窗口大小 - (<=x 的元素个数) = (>x 的元素个数)
left := i + 1 - k
if left < 0 { // 尚未形成第一个窗口
continue
}
// 2. 更新答案
ans = min(ans, inv)
if ans == 0 { // 已经最小了，无需再计算
break
}
// 3. 出
out := nums[left]
inv -= t.pre(out - 1)
t.update(out, -1)
}
return int64(ans)
}
# Accepted solution for LeetCode #3768: Minimum Inversion Count in Subarrays of Fixed Length
#
# @lc app=leetcode id=3768 lang=python3
#
# [3768] Minimum Inversion Count in Subarrays of Fixed Length
#
# @lc code=start
class Solution:
def minInversionCount(self, nums: List[int], k: int) -> int:
# Coordinate compression
sorted_unique = sorted(list(set(nums)))
rank_map = {val: i + 1 for i, val in enumerate(sorted_unique)}
m = len(sorted_unique)
# Fenwick Tree (BIT) implementation
bit = [0] * (m + 1)
def update(i, delta):
while i <= m:
bit[i] += delta
i += i & (-i)
def query(i):
s = 0
while i > 0:
s += bit[i]
i -= i & (-i)
return s
ranks = [rank_map[val] for val in nums]
n = len(nums)
current_inversions = 0
# Initialize first window
for i in range(k):
r = ranks[i]
# Count elements greater than current element already in window
# Elements processed so far is i
# Elements <= r is query(r)
# Elements > r is i - query(r)
greater_count = i - query(r)
current_inversions += greater_count
update(r, 1)
min_inversions = current_inversions
# Slide the window
for i in range(n - k):
leaving_rank = ranks[i]
entering_rank = ranks[i + k]
# Remove leaving element
# It contributed inversions equal to the count of elements smaller than it currently in the window
# We need to query BEFORE removing it from the BIT to get accurate count relative to current state
# Actually, the BIT contains exactly the elements of the current window.
# The leaving element is at index i (relative to nums), which is index 0 in the window.
# It forms inversions with elements to its right in the window that are smaller.
# So we subtract count of elements in BIT strictly smaller than leaving_rank.
smaller_than_leaving = query(leaving_rank - 1)
current_inversions -= smaller_than_leaving
update(leaving_rank, -1)
# Add entering element
# It forms inversions with elements to its left in the window that are larger.
# The entering element is at the end of the new window.
# We add count of elements in BIT strictly larger than entering_rank.
# Current size of window in BIT is k-1 (since we just removed one).
larger_than_entering = (k - 1) - query(entering_rank)
current_inversions += larger_than_entering
update(entering_rank, 1)
if current_inversions < min_inversions:
min_inversions = current_inversions
return min_inversions
# @lc code=end
// Accepted solution for LeetCode #3768: Minimum Inversion Count in Subarrays of Fixed Length
// Rust example auto-generated from go reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (go):
// // Accepted solution for LeetCode #3768: Minimum Inversion Count in Subarrays of Fixed Length
// package main
//
// import (
// "math"
// "slices"
// "sort"
// )
//
// // https://space.bilibili.com/206214
// type fenwick []int
//
// func (t fenwick) update(i, val int) {
// for ; i < len(t); i += i & -i {
// t[i] += val
// }
// }
//
// func (t fenwick) pre(i int) (res int) {
// for ; i > 0; i &= i - 1 {
// res += t[i]
// }
// return
// }
//
// func minInversionCount(nums []int, k int) int64 {
// // 离散化
// sorted := slices.Clone(nums)
// slices.Sort(sorted)
// sorted = slices.Compact(sorted)
// for i, x := range nums {
// nums[i] = sort.SearchInts(sorted, x) + 1
// }
//
// t := make(fenwick, len(sorted)+1)
// inv := 0
// ans := math.MaxInt
//
// for i, in := range nums {
// // 1. 入
// t.update(in, 1)
// inv += min(i+1, k) - t.pre(in) // 窗口大小 - (<=x 的元素个数) = (>x 的元素个数)
//
// left := i + 1 - k
// if left < 0 { // 尚未形成第一个窗口
// continue
// }
//
// // 2. 更新答案
// ans = min(ans, inv)
// if ans == 0 { // 已经最小了，无需再计算
// break
// }
//
// // 3. 出
// out := nums[left]
// inv -= t.pre(out - 1)
// t.update(out, -1)
// }
// return int64(ans)
// }
// Accepted solution for LeetCode #3768: Minimum Inversion Count in Subarrays of Fixed Length
// Auto-generated TypeScript example from go.
function exampleSolution(): void {
}
// Reference (go):
// // Accepted solution for LeetCode #3768: Minimum Inversion Count in Subarrays of Fixed Length
// package main
//
// import (
// "math"
// "slices"
// "sort"
// )
//
// // https://space.bilibili.com/206214
// type fenwick []int
//
// func (t fenwick) update(i, val int) {
// for ; i < len(t); i += i & -i {
// t[i] += val
// }
// }
//
// func (t fenwick) pre(i int) (res int) {
// for ; i > 0; i &= i - 1 {
// res += t[i]
// }
// return
// }
//
// func minInversionCount(nums []int, k int) int64 {
// // 离散化
// sorted := slices.Clone(nums)
// slices.Sort(sorted)
// sorted = slices.Compact(sorted)
// for i, x := range nums {
// nums[i] = sort.SearchInts(sorted, x) + 1
// }
//
// t := make(fenwick, len(sorted)+1)
// inv := 0
// ans := math.MaxInt
//
// for i, in := range nums {
// // 1. 入
// t.update(in, 1)
// inv += min(i+1, k) - t.pre(in) // 窗口大小 - (<=x 的元素个数) = (>x 的元素个数)
//
// left := i + 1 - k
// if left < 0 { // 尚未形成第一个窗口
// continue
// }
//
// // 2. 更新答案
// ans = min(ans, inv)
// if ans == 0 { // 已经最小了，无需再计算
// break
// }
//
// // 3. 出
// out := nums[left]
// inv -= t.pre(out - 1)
// t.update(out, -1)
// }
// return int64(ans)
// }
Use this to step through a reusable interview workflow for this problem.
For each of q queries, scan the entire range to compute the aggregate (sum, min, max). Each range scan takes up to O(n) for a full-array query. With q queries: O(n × q) total. Point updates are O(1) but queries dominate.
Building the tree is O(n). Each query or update traverses O(log n) nodes (tree height). For q queries: O(n + q log n) total. Space is O(4n) ≈ O(n) for the tree array. Lazy propagation adds O(1) per node for deferred updates.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Using `if` instead of `while` leaves the window invalid for multiple iterations.
Usually fails on: Over-limit windows stay invalid and produce wrong lengths/counts.
Fix: Shrink in a `while` loop until the invariant is valid again.