LeetCode 629 - K Inverse Pairs Array

Here’s a full technical solution guide following your formatting rules for LeetCode 629: The problem asks us to determine the number of arrays of length n containing numbers from 1 to n such that there are exactly k inverse pairs.

leetcodeharddynamic-programming

LeetCode Problem 629

Difficulty: 🔴 Hard
Topics: Dynamic Programming

Solution

Here’s a full technical solution guide following your formatting rules for LeetCode 629:

Problem Understanding

The problem asks us to determine the number of arrays of length n containing numbers from 1 to n such that there are exactly k inverse pairs. An inverse pair [i, j] occurs when i < j and nums[i] > nums[j]. In other words, it counts the number of elements that are out of order relative to the sorted array.

The input consists of two integers, n and k. n defines the size of the permutation and the maximum number that can appear in the array, while k specifies the exact number of inverse pairs we are trying to count. The output is a single integer representing the count of valid arrays modulo 10^9 + 7.

Constraints tell us that n and k can go up to 1000. This implies that naive brute-force solutions, such as generating all n! permutations and counting their inverse pairs, are completely infeasible due to factorial growth.

Important edge cases include k = 0 (only the sorted array is valid), k equal to the maximum number of inverse pairs for n (fully reversed array), and cases where k is larger than the maximum possible inverse pairs (n*(n-1)/2), which should return 0.

Approaches

A brute-force approach would generate all permutations of numbers from 1 to n and count the number of inverse pairs for each permutation. While correct, it is extremely slow because the number of permutations is n!, which grows factorially and becomes computationally infeasible for n > 10.

The key insight for an optimal solution is dynamic programming. Let dp[i][j] be the number of arrays of length i with exactly j inverse pairs. When we add the next number i to arrays of length i-1, placing it at different positions generates different numbers of new inverse pairs. By recognizing that placing i at index p from the end adds p new inverse pairs, we can derive a recursive relation that allows filling a DP table efficiently. Further, using prefix sums or cumulative sums can reduce repeated calculations to achieve an O(n*k) solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(n! * n) O(n) Generate all permutations and count inverse pairs. Infeasible for n > 10.
Optimal O(n*k) O(k) Dynamic programming with prefix sums for efficiency. Handles large n and k.

Algorithm Walkthrough

  1. Initialize a 1D DP array of size k+1 representing dp[j] for the number of arrays with exactly j inverse pairs.
  2. Set dp[0] = 1, because there is exactly one array of length 1 with 0 inverse pairs.
  3. Iterate over i from 2 to n. For each i, compute a new DP array new_dp:

a. Use a cumulative sum array to efficiently compute the sum of valid previous states that can contribute to j inverse pairs.

b. For j from 0 to k, calculate the number of arrays by adding i at different positions relative to arrays of length i-1. 4. Use modulo 10^9 + 7 at each addition to prevent overflow. 5. After processing all numbers up to n, dp[k] contains the desired count of arrays.

Why it works: Each DP entry dp[i][j] correctly counts the number of arrays of length i with j inverse pairs because the algorithm considers all ways of inserting the new number i and updates the count cumulatively, maintaining the invariant that all counted arrays are distinct permutations with the exact number of inverse pairs.

Python Solution

class Solution:
    def kInversePairs(self, 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)
            cum_sum = 0
            for j in range(k + 1):
                cum_sum += dp[j]
                if j >= i:
                    cum_sum -= dp[j - i]
                new_dp[j] = cum_sum % MOD
            dp = new_dp
        
        return dp[k]

In this Python implementation, dp keeps track of the number of arrays for each possible inverse pair count. For each new number i, a cumulative sum technique is used to efficiently calculate all possible new inverse pairs without nested loops, ensuring an O(n*k) solution.

Go Solution

func kInversePairs(n int, k int) int {
    const MOD = 1e9 + 7
    dp := make([]int, k+1)
    dp[0] = 1

    for i := 1; i <= n; i++ {
        newDp := make([]int, k+1)
        cumSum := 0
        for j := 0; j <= k; j++ {
            cumSum += dp[j]
            if j >= i {
                cumSum -= dp[j-i]
            }
            newDp[j] = (cumSum % MOD + MOD) % MOD
        }
        dp = newDp
    }

    return dp[k]
}

In Go, slices are used instead of arrays for dynamic allocation. Integer overflow is explicitly handled using modulo operations. The logic mirrors Python, but care is taken to ensure non-negative modulo results, which is common in Go.

Worked Examples

Example 1: n = 3, k = 0

i dp state Explanation
1 [1,0,0,0] Only 1 array of length 1 with 0 inverse pairs
2 [1,1,0,0] Adding 2 creates arrays [1,2] (0 pairs), [2,1] (1 pair)
3 [1,2,2,1] Adding 3 creates arrays with 0,1,2,3 inverse pairs

Result: dp[0] = 1

Example 2: n = 3, k = 1

i dp state Explanation
1 [1,0,0,0] Base case
2 [1,1,0,0] As above
3 [1,2,2,1] Arrays with 1 inverse pair: [1,3,2], [2,1,3]

Result: dp[1] = 2

Complexity Analysis

Measure Complexity Explanation
Time O(n*k) Outer loop over n, inner loop over k. Using cumulative sum avoids an extra nested loop of size i.
Space O(k) Only two arrays of size k+1 are maintained at a time.

This is efficient for the given constraints, since n and k ≤ 1000.

Test Cases

# provided examples
assert Solution().kInversePairs(3, 0) == 1  # 0 inverse pairs
assert Solution().kInversePairs(3, 1) == 2  # 1 inverse pair

# boundary tests
assert Solution().kInversePairs(1, 0) == 1  # smallest n
assert Solution().kInversePairs(1, 1) == 0  # impossible

# stress tests
assert Solution().kInversePairs(1000, 0) == 1  # only sorted array
assert Solution().kInversePairs(1000, 1000) >= 0  # large n, k

# maximum inverse pairs
assert Solution().kInversePairs(3, 3) == 1  # fully reversed array
Test Why
n=3, k=0 Verifies base case with 0 inverse pairs
n=3, k=1 Checks intermediate number of inverse pairs
n=1, k=0 Smallest array
n=1, k=1 Impossible inverse pairs, should return 0
n=1000, k=0 Large n with minimal k, verifies performance
n=3, k=3 Maximum possible inverse pairs for n=3

Edge Cases

Case 1: Zero inverse pairs

When k = 0, only the sorted array [1,2,...,n] is valid. The implementation correctly handles this because dp[0] is initialized to 1 and cumulative sum logic does not generate negative pairs.

Case 2: Maximum inverse pairs

For k = n*(n-1)/2, only the fully reversed array is valid. The cumulative sum technique correctly sums contributions from inserting numbers at the maximum inverse positions, so the algorithm counts exactly one array.

Case 3: Impossible k

If k > n*(n-1)/2, no array can have that many inverse pairs. Our algorithm naturally returns 0 in such cases because cumulative sum never