629 - K Inverse Pairs Array

Difficulty: Hard | Pattern: Dynamic Programming | Company tags: Google, Amazon

Problem Statement

For an integer array nums, an inverse pair is a pair of integers [nums[i], nums[j]] where 0 <= i < j < nums.length and nums[i] > nums[j].

Given two integers n and k, return the number of different arrays consisting of numbers from 1 to n such that there are exactly k inverse pairs. Since the answer can be huge, return it modulo 10^9 + 7.

Example 1:

Input: n = 3, k = 0
Output: 1  (only [1,2,3])

Example 2:

Input: n = 3, k = 1
Output: 2  ([1,3,2] and [2,1,3])

Approach: DP with Sliding Window — O(nk), O(k)

Key insight: When we insert n into an array of size n-1:

• Placing n at position n-1 (rightmost) adds 0 new inverse pairs
• Placing n at position n-2 adds 1 new inverse pair
• ...placing at position 0 adds n-1 inverse pairs

So dp[i][j] = sum(dp[i-1][j-t]) for t in 0..min(j, i-1) — a sliding window sum.

Algorithm Flow

def kInversePairs(n: int, k: int) -> int:
    MOD = 10**9 + 7
    dp = [0] * (k + 1)
    dp[0] = 1
    
    for i in range(1, n + 1):
        new_dp = [0] * (k + 1)
        window = 0
        for j in range(k + 1):
            window += dp[j]
            if j >= i:
                window -= dp[j - i]
            new_dp[j] = window % MOD
        dp = new_dp
    
    return dp[k]

Dry Run

n=3, k=1

Start: dp=[1,0,0] (n=1: only [1], 0 inverse pairs)

n=2: window sums over dp, each element can add 0 or 1 inverse pair

• dp=[1,1,0] (one way for 0 pairs: [1,2]; one way for 1 pair: [2,1])

n=3: each element can add 0,1,2 inverse pairs

• j=0: window=dp[0]=1 → new_dp[0]=1
• j=1: window=dp[0]+dp[1]=2 → new_dp[1]=2

dp[1] = 2 ✓

Complexity

• Time: O(nk)
• Space: O(k)

Key Terms

Term	Definition
Inverse pair	Indices i < j with nums[i] > nums[j]
Sliding window sum	Running sum maintained incrementally by adding/removing one element per step instead of recomputing
DP state compression	Reducing a 2D DP table to a 1D rolling array since dp[i] only depends on dp[i-1]
Prefix sum	Cumulative sum used to answer range-sum queries in O(1)

FAQ

1. Why does inserting n create inverse pairs based on position? Placing the value n (the largest so far) at position p from the right creates exactly that many new inverse pairs, since every element to its right is smaller.
2. Can this be solved without the sliding window optimization? Yes, with a naive O(n·k²) DP that sums dp[i-1][j-t] for all t directly, but it's too slow for large k.
3. What if k is larger than the maximum possible inverse pairs (n*(n-1)/2)? The answer is 0; the DP array naturally yields 0 since no arrangement reaches that many pairs.
4. Why take modulo 10^9 + 7 inside the loop rather than at the end? Because window accumulates over many additions and could overflow or grow unboundedly; taking mod each step keeps values bounded.
5. How is this related to counting permutations by inversions? It is the classic "Mahonian numbers" problem — counting permutations of 1..n by exact inversion count.

Quick Revision

• Problem: count permutations of 1..n with exactly k inversions, mod 1e9+7.
• Build arrays incrementally: insert i into a permutation of size i-1.
• Inserting i at position p from the right adds p new inverse pairs (0 to i-1 options).
• dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-i] (sliding window sum recurrence).
• Maintain a running window sum instead of summing a range each time — this is what makes it O(nk).
• Use a 1D rolling array since each row only depends on the previous row.
• Apply modulo after every addition/subtraction to avoid overflow and keep values non-negative.
• Answer is dp[n][k] after processing all n insertions.

Related Problems

• 96 - Unique Binary Search Trees — counting DP with similar recurrence structure
• 368 - Largest Divisible Subset — DP over ordered sequences
• Pattern match: counting DP problems with sliding-window recurrence (e.g. "Coin Change II")