LeetCode 3768 - Minimum Inversion Count in Subarrays of Fixed Length

We are given an array nums of length n and an integer k. For every contiguous subarray of length k, we must compute its inversion count, then return the smallest inversion count among all such windows.

leetcodehardarraysegment-treesliding-window

LeetCode Problem 3768

Difficulty: 🔴 Hard
Topics: Array, Segment Tree, Sliding Window

Solution

LeetCode 3768 - Minimum Inversion Count in Subarrays of Fixed Length

Problem Understanding

We are given an array nums of length n and an integer k. For every contiguous subarray of length k, we must compute its inversion count, then return the smallest inversion count among all such windows.

An inversion is a pair of indices (i, j) such that:

  • i < j
  • nums[i] > nums[j]

The inversion count of a subarray is simply the number of such pairs that exist entirely inside that subarray.

The task is therefore:

  1. Consider every contiguous subarray of length k.
  2. Compute the inversion count of each subarray.
  3. Return the minimum inversion count observed.

The constraints are the key challenge:

  • n ≤ 100000
  • nums[i] ≤ 10^9

A quadratic solution is completely impossible. Even an O(nk) solution fails when both n and k are large.

The values themselves can be as large as 10^9, which means we cannot directly use them as indices in a Fenwick Tree or Segment Tree. Coordinate compression is required.

Several important edge cases immediately stand out.

When k = 1, every window contains exactly one element, so the inversion count is always zero.

When k = n, there is only one window, namely the entire array.

Arrays may contain duplicate values. Since an inversion requires nums[i] > nums[j], equal values do not contribute to the inversion count.

The inversion count can be as large as k(k-1)/2, which for k = 100000 is approximately 5 × 10^9, so 64-bit integers are required.

Approaches

Brute Force

The most direct approach is to examine every window of length k.

For each window, we check every pair of indices inside the window and count how many satisfy the inversion condition.

If there are n-k+1 windows and each window requires O(k²) work, the total complexity becomes:

O((n-k+1) · k²)

This is far too slow. For n = k = 100000, the work would be on the order of 10^10 operations.

Even a slightly improved approach that computes each window's inversion count independently using a Fenwick Tree would still require O((n-k+1) · k log n), which is also too expensive.

Key Observation

The windows differ by only one element.

When sliding from:

[l, r]

to

[l+1, r+1]

exactly one element leaves the window and one element enters.

Instead of recomputing the inversion count from scratch, we can update it incrementally.

Suppose:

  • x = nums[l] leaves
  • y = nums[r+1] enters

The inversion count changes only through pairs involving these two elements.

If we can efficiently determine:

  • how many inversion pairs disappear when x leaves,
  • how many inversion pairs appear when y enters,

then we can maintain the inversion count while sliding.

This requires a data structure that supports:

  • insert value,
  • remove value,
  • count elements less than a value,
  • count elements greater than a value.

A Fenwick Tree after coordinate compression provides all these operations in O(log n) time.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O((n-k+1)·k²) O(1) Check every pair in every window
Optimal O(n log n) O(n) Sliding window inversion maintenance using Fenwick Tree

Algorithm Walkthrough

Coordinate Compression

The array values can be as large as 10^9.

Fenwick Trees require indices in a compact range, so we sort the distinct values and map each value to its rank.

After compression every number lies in:

[1, m]

where m ≤ n.

Build the First Window Inversion Count

We compute the inversion count of the first window using a Fenwick Tree.

Process elements from left to right.

For each element:

  1. Count how many previous elements are greater than it.
  2. Add that count to the inversion total.
  3. Insert the element into the Fenwick Tree.

After processing the first k elements, we know the inversion count of the initial window.

Maintain a Second Fenwick Tree

After the first window is built, create a Fenwick Tree representing the current window's multiset.

This tree allows us to answer:

  • number of elements less than a value,
  • number of elements greater than a value,

inside the current window.

Remove the Leftmost Element

Suppose x leaves the window.

Inside the current window, x is always the leftmost position.

Every inversion involving x has the form:

x > other

with the other element appearing later.

The number of such pairs equals:

count(elements < x in current window)

Before removing x, subtract this amount from the inversion count.

Then remove x from the Fenwick Tree.

Add the New Rightmost Element

Suppose y enters from the right.

It becomes the last position of the new window.

Every new inversion involving y has the form:

other > y

where other is already in the window.

The number of such pairs equals:

count(elements > y in current window)

Add this amount to the inversion count.

Then insert y into the Fenwick Tree.

Update the Answer

After every slide:

  1. Current inversion count is known.
  2. Update the minimum answer.

Repeat until all windows have been processed.

Why it works

At every step, the maintained inversion count equals the number of inversion pairs inside the current window.

When the leftmost element leaves, every inversion involving it disappears. Since it is the earliest index in the window, all such inversions are exactly the elements smaller than it.

When a new element enters on the right, every new inversion involving it comes from earlier elements larger than it.

No other inversion pairs change during the slide. Therefore the update exactly transforms the old window's inversion count into the new window's inversion count.

By examining every window once, the minimum inversion count is found correctly.

Python Solution

from typing import List

class Fenwick:
    def __init__(self, n: int):
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, idx: int, delta: int) -> None:
        while idx <= self.n:
            self.bit[idx] += delta
            idx += idx & -idx

    def query(self, idx: int) -> int:
        res = 0
        while idx > 0:
            res += self.bit[idx]
            idx -= idx & -idx
        return res

    def range_query(self, left: int, right: int) -> int:
        if left > right:
            return 0
        return self.query(right) - self.query(left - 1)

class Solution:
    def minInversionCount(self, nums: List[int], k: int) -> int:
        n = len(nums)

        values = sorted(set(nums))
        rank = {v: i + 1 for i, v in enumerate(values)}
        compressed = [rank[x] for x in nums]

        m = len(values)

        build_bit = Fenwick(m)
        inversions = 0

        for i in range(k):
            x = compressed[i]
            inversions += i - build_bit.query(x)
            build_bit.add(x, 1)

        answer = inversions

        window_bit = Fenwick(m)
        for i in range(k):
            window_bit.add(compressed[i], 1)

        for left in range(n - k):
            outgoing = compressed[left]

            removed_pairs = window_bit.query(outgoing - 1)
            inversions -= removed_pairs

            window_bit.add(outgoing, -1)

            incoming = compressed[left + k]

            window_size = k - 1
            greater_count = (
                window_size - window_bit.query(incoming)
            )

            inversions += greater_count

            window_bit.add(incoming, 1)

            answer = min(answer, inversions)

        return answer

Implementation Explanation

The first section performs coordinate compression so that all values fit into a compact range suitable for Fenwick Tree indexing.

A Fenwick Tree named build_bit computes the inversion count of the initial window. For every element, the number of previous elements greater than it equals:

i - build_bit.query(x)

because build_bit.query(x) counts previous elements less than or equal to the current value.

A second Fenwick Tree named window_bit stores the frequency distribution of the current window.

When sliding:

  • window_bit.query(outgoing - 1) counts elements smaller than the outgoing value, which are exactly the inversion pairs that disappear.
  • After removal, the window contains k-1 elements.
  • window_size - window_bit.query(incoming) counts elements strictly greater than the incoming value, which are exactly the new inversion pairs created.

The inversion count is updated in O(log n) time per slide.

Go Solution

func minInversionCount(nums []int, k int) int64 {
	n := len(nums)

	valsMap := make(map[int]struct{})
	for _, v := range nums {
		valsMap[v] = struct{}{}
	}

	vals := make([]int, 0, len(valsMap))
	for v := range valsMap {
		vals = append(vals, v)
	}

	sort.Ints(vals)

	rank := make(map[int]int)
	for i, v := range vals {
		rank[v] = i + 1
	}

	comp := make([]int, n)
	for i, v := range nums {
		comp[i] = rank[v]
	}

	m := len(vals)

	bit1 := NewFenwick(m)

	var inversions int64

	for i := 0; i < k; i++ {
		x := comp[i]
		inversions += int64(i - bit1.Query(x))
		bit1.Add(x, 1)
	}

	answer := inversions

	windowBit := NewFenwick(m)
	for i := 0; i < k; i++ {
		windowBit.Add(comp[i], 1)
	}

	for left := 0; left < n-k; left++ {
		outgoing := comp[left]

		removedPairs := int64(windowBit.Query(outgoing - 1))
		inversions -= removedPairs

		windowBit.Add(outgoing, -1)

		incoming := comp[left+k]

		greaterCount := int64((k - 1) - windowBit.Query(incoming))
		inversions += greaterCount

		windowBit.Add(incoming, 1)

		if inversions < answer {
			answer = inversions
		}
	}

	return answer
}

type Fenwick struct {
	n   int
	bit []int
}

func NewFenwick(n int) *Fenwick {
	return &Fenwick{
		n:   n,
		bit: make([]int, n+1),
	}
}

func (f *Fenwick) Add(idx int, delta int) {
	for idx <= f.n {
		f.bit[idx] += delta
		idx += idx & -idx
	}
}

func (f *Fenwick) Query(idx int) int {
	res := 0
	for idx > 0 {
		res += f.bit[idx]
		idx -= idx & -idx
	}
	return res
}

Go Specific Notes

The inversion count may exceed 32-bit range, so int64 is used for both the running inversion count and the returned result.

The Fenwick Tree stores frequencies, which never exceed 100000, so regular int is sufficient inside the tree.

Go requires explicit coordinate compression and helper structures because there is no built in ordered map.

Worked Examples

Example 1

nums = [3,1,2,5,4]
k = 3

Compressed values:

[3,1,2,5,4]

First window:

[3,1,2]
Step Value New Inversions Total
0 3 0 0
1 1 1 1
2 2 1 2

Current inversion count:

2

Slide to:

[1,2,5]

Outgoing:

3

Smaller elements:

1,2

Removed inversions:

2

New count:

0

Incoming:

5

Greater elements already present:

0

Final count:

0

Minimum becomes:

0

Slide again:

[2,5,4]

Outgoing:

1

Removed pairs:

0

Incoming:

4

Greater elements:

5

Added pairs:

1

Count:

1

Minimum remains:

0

Answer:

0

Example 2

nums = [5,3,2,1]
k = 4

Only one window exists.

All pairs are inversions:

(5,3)
(5,2)
(5,1)
(3,2)
(3,1)
(2,1)

Total:

6

Answer:

6

Example 3

nums = [2,1]
k = 1

Windows:

[2]
[1]

Every window has:

0 inversions

Answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Coordinate compression plus one Fenwick update/query sequence per element
Space O(n) Compression arrays, mapping, and Fenwick Trees

The coordinate compression phase requires sorting distinct values, which costs O(n log n). Building the first window and processing every slide each require only a constant number of Fenwick operations, each costing O(log n). Therefore the total complexity remains O(n log n).

Test Cases

sol = Solution()

assert sol.minInversionCount([3, 1, 2, 5, 4], 3) == 0  # example 1
assert sol.minInversionCount([5, 3, 2, 1], 4) == 6     # example 2
assert sol.minInversionCount([2, 1], 1) == 0           # example 3

assert sol.minInversionCount([1], 1) == 0              # smallest input
assert sol.minInversionCount([1, 2, 3, 4], 4) == 0    # fully sorted
assert sol.minInversionCount([4, 3, 2, 1], 4) == 6    # fully reversed

assert sol.minInversionCount([1, 1, 1, 1], 2) == 0    # duplicates only
assert sol.minInversionCount([2, 2, 1], 2) == 0       # duplicate handling

assert sol.minInversionCount([5, 4, 3, 2, 1], 2) == 1 # every window has one inversion
assert sol.minInversionCount([1, 5, 2, 6, 3], 3) == 1 # mixed ordering

assert sol.minInversionCount([1, 2, 3, 4, 5], 1) == 0 # k = 1
assert sol.minInversionCount([5, 4, 3, 2, 1], 1) == 0 # k = 1 reversed

Test Summary

Test Why
[3,1,2,5,4], k=3 Official example
[5,3,2,1], k=4 Single window
[2,1], k=1 Minimum window size
[1], k=1 Smallest valid input
Sorted array Zero inversions
Reversed array Maximum inversions
All duplicates Equal values are not inversions
Duplicate mixed values Tests strict greater than rule
Descending with k=2 Small fixed window
Mixed ordering General correctness
Sorted with k=1 Trivial windows
Reversed with k=1 Trivial windows regardless of order

Edge Cases

Window Size Equals One

When k = 1, every window contains exactly one element. Since an inversion requires two distinct indices, the inversion count is always zero. A buggy implementation might accidentally count self pairs or mishandle sliding updates. The presented solution naturally returns zero because no inversions are added during initialization or sliding.

Window Size Equals Array Length

When k = n, there is only one valid window. Some sliding window implementations incorrectly assume at least one slide will occur. Here, the sliding loop executes zero times, and the answer is simply the inversion count computed for the initial window.

Duplicate Values

An inversion requires a strict inequality, nums[i] > nums[j]. Equal values must not be counted. The Fenwick Tree queries are carefully written so that elements equal to the target value are excluded from both the "smaller than" and "greater than" counts. This guarantees duplicates are handled correctly.

Very Large Inversion Counts

For large windows, the inversion count can exceed two billion. For example, a reversed array of length 100000 contains nearly five billion inversions. Using 32-bit integers would overflow. The solution therefore stores inversion counts in 64-bit variables, specifically int64 in Go and Python's arbitrary precision integers in Python.

Large Value Range

The array values may be as large as 10^9. Direct indexing into a Fenwick Tree would be impossible. Coordinate compression maps values into a dense range [1, m], preserving ordering while keeping the Fenwick Tree size at O(n).