LeetCode 629: K Inverse Pairs Array Solution in Python – A Step-by-Step Guide

What Is LeetCode 629: K Inverse Pairs Array?

In LeetCode 629: K Inverse Pairs Array, you’re given two integers: n (array length, 1 to n) and k (number of inverse pairs), and your task is to count how many distinct arrays can be formed with exactly k inverse pairs, returning the result modulo 10⁹ + 7 (1,000,000,007). An inverse pair is a pair (i, j) where i < j and nums[i] > nums[j]. For example, with n = 3, k = 1, arrays like [2, 3, 1] and [3, 1, 2] each have 1 inverse pair. This problem tests your ability to handle combinatorial counting with dynamic programming under modulo arithmetic.

Problem Statement

• Input:
• n: Integer (array length, 1 ≤ n ≤ 1000).
• k: Integer (inverse pairs, 0 ≤ k ≤ 1000).
• Output: An integer—number of arrays with exactly k inverse pairs, modulo 10⁹ + 7.
• Rules:
• Array uses numbers 1 to n exactly once.
• Count inverse pairs (i, j) where i < j and nums[i] > nums[j].
• Return result % (10⁹ + 7).

Constraints

• 1 ≤ n ≤ 1000.
• 0 ≤ k ≤ 1000.

Examples

• Input: n = 3, k = 0
• Output: 1 (Only [1, 2, 3] has 0 inverse pairs)
• Input: n = 3, k = 1
• Output: 2 ([2, 1, 3], [3, 1, 2])
• Input: n = 4, k = 2
• Output: 4 ([2, 3, 1, 4], [2, 4, 1, 3], [3, 1, 2, 4], [4, 1, 2, 3])

These examples set the stage—let’s solve it!

Understanding the Problem: Counting Inverse Pairs

To solve LeetCode 629: K Inverse Pairs Array in Python, we need to count permutations of numbers 1 to n with exactly k inverse pairs, handling large results with modulo 10⁹ + 7. A brute-force approach—generating all permutations and counting pairs—is O(n!), infeasible for n up to 1000. Instead, we’ll use dynamic programming or recursion to build the count efficiently. We’ll explore:

• Best Solution (DP with Cumulative Sums): O(n * k) time, O(k) space—fast and optimized.
• Alternative Solution (Recursive with Memoization): O(n k) time, O(n k) space—intuitive but heavier.

Let’s start with the DP solution, breaking it down for beginners.

Best Solution: Dynamic Programming with Cumulative Sums

Why This Is the Best Solution

The DP with cumulative sums approach is the top choice for LeetCode 629 because it’s efficient—O(n * k) time with O(k) space—and optimizes space by using a rolling array while leveraging cumulative sums to reduce computation. It fits constraints (n, k ≤ 1000) and handles modulo arithmetic seamlessly. It’s like building a counting grid step-by-step, refining it as you go!

How It Works

Think of this as counting arrays incrementally:

• Step 1: Define DP:
• dp[j]: Number of arrays of length i with j inverse pairs.
• Step 2: Base Case:
• n = 1, k = 0: 1 way ([1]).
• Step 3: Transition:
• For array of length i, add number i:
• Place i at end: 0 new inversions (dp[j] from i-1).
• Place i at second-to-last: 1 inversion (dp[j-1] from i-1).
• Up to i-1 inversions (min(j, i-1) positions).
• dp[j] = sum(dp[j-x] for x = 0 to min(j, i-1)).
• Step 4: Optimize with Cumulative Sums:
• Use sliding window to compute sums efficiently.
• Step 5: Modulo and Return:
• Apply % (10⁹ + 7), return dp[k].

It’s like a counting conveyor—build and sum!

Step-by-Step Example

Example: n = 3, k = 1

• Step 1: Init:
• dp = [0] * (k + 1) = [0, 0].
• Mod = 10⁹ + 7.
• Step 2: n = 1:
• dp[0] = 1 ([1]).
• dp = [1, 0].
• Step 3: n = 2:
• j = 0: dp[0] = dp[0] = 1 ([1, 2]).
• j = 1: dp[1] = dp[0] = 1 ([2, 1]).
• dp = [1, 1].
• Step 4: n = 3:
• j = 0: dp[0] = dp[0] = 1 ([1, 2, 3]).
• j = 1: dp[1] = dp[0] + dp[1] = 1 + 1 = 2 ([2, 1, 3], [3, 1, 2]).
• dp = [1, 2].
• Step 5: Return dp[1] = 2.
• Output: 2.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        # Step 1: Initialize constants and DP array
        MOD = 10**9 + 7
        dp = [0] * (k + 1)
        dp[0] = 1  # Base case: 1 way for k=0 with n=1

        # Step 2: Iterate over array lengths
        for i in range(2, n + 1):
            # Step 3: Create new DP array for current length
            new_dp = [0] * (k + 1)
            new_dp[0] = 1  # 0 inversions with sorted array

            # Step 4: Compute cumulative sum for efficiency
            curr_sum = dp[0]  # Sum of dp[j-x] up to current j
            for j in range(1, k + 1):
                # Add previous dp value if within bounds
                if j - i >= 0:
                    curr_sum = (curr_sum - dp[j - i] + MOD) % MOD
                curr_sum = (curr_sum + dp[j]) % MOD
                new_dp[j] = curr_sum

            # Update dp for next iteration
            dp = new_dp

        # Step 5: Return result for k inverse pairs
        return dp[k]

• Lines 4-6: Init: dp for k+1 slots, base case dp[0] = 1.
• Lines 9-21: Iterate:
• New dp per length, compute sums with sliding window.
• Adjust curr_sum to avoid recomputing.
• Line 24: Return dp[k] modulo 10⁹ + 7.
• Time Complexity: O(n * k)—n lengths, k inversions.
• Space Complexity: O(k)—rolling array.

This is like a counting machine—efficient and sleek!

Alternative Solution: Recursive with Memoization

Why an Alternative Approach?

The recursive with memoization approach builds the solution top-down—O(n * k) time, O(n * k) space. It’s more intuitive, breaking the problem into subproblems, but uses more memory due to the memo table. It’s like exploring all paths and caching results!

How It Works

Picture this as a recursive explorer:

• Step 1: Define recursive function:
• f(n, k): Ways for length n with k inversions.
• Step 2: Base cases:
• n = 1, k = 0: 1 way.
• k < 0: 0 ways.
• Step 3: Recurrence:
• Place n at end: f(n-1, k).
• Place n earlier: Add 1 to n-1 inversions, up to n-1.
• f(n, k) = sum(f(n-1, k-x) for x = 0 to min(k, n-1)).
• Step 4: Memoize and modulo.
• Step 5: Return result.

It’s like a path counter—intuitive but heavy!

Step-by-Step Example

Example: n = 3, k = 1

• Step 1: Call f(3, 1):
• f(2, 1): 1 + 0.
• f(2, 0): 1.
• Step 2: f(2, 1):
• f(1, 1): 0.
• f(1, 0): 1.
• Total: 1.
• Step 3: f(3, 1) = 1 + 1 = 2.
• Output: 2.

Code for Recursive Approach

class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        MOD = 10**9 + 7
        memo = {}

        def f(n, k):
            if k < 0:
                return 0
            if n == 1:
                return 1 if k == 0 else 0
            if (n, k) in memo:
                return memo[(n, k)]

            result = 0
            for x in range(min(k, n - 1) + 1):
                result = (result + f(n - 1, k - x)) % MOD

            memo[(n, k)] = result
            return result

        return f(n, k)

• Lines 4-5: Init memo and MOD.
• Lines 7-19: Recursive function:
• Base cases, memo check, sum subproblems.
• Time Complexity: O(n k)—n k states.
• Space Complexity: O(n * k)—memo table.

It’s a recursive counter—clear but bulky!

Comparing the Two Solutions

• DP with Sums (Best):
• Pros: O(n * k) time, O(k) space, fast and space-efficient.
• Cons: Less intuitive.
• Recursive (Alternative):
• Pros: O(n k) time, O(n k) space, intuitive recursion.
• Cons: More memory, slightly slower.

DP wins for efficiency.

Additional Examples and Edge Cases

• Input: n = 1, k = 0
• Output: 1.
• Input: n = 2, k = 2
• Output: 0 (max inversions = 1).

Both handle these well.

Complexity Breakdown

• DP: Time O(n * k), Space O(k).
• Recursive: Time O(n k), Space O(n k).

DP is optimal.

Key Takeaways

• DP: Cumulative efficiency—smart!
• Recursive: Memoized exploration—clear!
• Counting: Combinatorics is fun.
• Python Tip: DP rocks—see Python Basics.

Final Thoughts: Count Those Arrays

LeetCode 629: K Inverse Pairs Array in Python is a challenging combinatorics puzzle. DP with cumulative sums offers speed and space savings, while recursive memoization provides clarity. Want more? Try LeetCode 96: Unique Binary Search Trees or LeetCode 377: Combination Sum IV. Ready to count? Head to Solve LeetCode 629 on LeetCode and tally those inverse pairs today!