Skip to main content
Talentd

K Inverse Pairs Array - Solution & Explanation

HardDynamic Programming16 min readAsked at: Microsoft, Meta, Google +1
Practice this problem

Problem Statement

For an integer array nums, an inverse pair is a pair of integers [i, 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 109 + 7.

 

Example 1:

Input: n = 3, k = 0
Output: 1
Explanation: Only the array [1,2,3] which consists of numbers from 1 to 3 has exactly 0 inverse pairs.

Example 2:

Input: n = 3, k = 1
Output: 2
Explanation: The array [1,3,2] and [2,1,3] have exactly 1 inverse pair.

 

Constraints:

  • 1 <= n <= 1000
  • 0 <= k <= 1000

Approach Overview

Problem Overview: Given integers n and k, count how many permutations of numbers 1..n contain exactly k inverse pairs. An inverse pair exists when i < j but nums[i] > nums[j]. The result can be very large, so the answer is returned modulo 1e9 + 7.

Approach 1: Dynamic Programming (Naive Transition) (Time: O(n*k*n), Space: O(n*k))

Define dp[i][j] as the number of arrays formed using numbers 1..i that contain exactly j inverse pairs. When inserting the number i into a permutation of size i-1, placing it at different positions creates additional inverse pairs. If you place i at position p from the end, it contributes p new inverse pairs. The transition becomes dp[i][j] = sum(dp[i-1][j-x]) for all valid x where 0 ≤ x < i. This directly simulates every possible insertion position, but the nested summation makes the time complexity O(n*k*n), which is too slow for large inputs.

Approach 2: Dynamic Programming with Prefix Sum Optimization (Time: O(n*k), Space: O(n*k))

The key observation is that the recurrence above repeatedly sums overlapping ranges. Instead of recomputing each sum, maintain a prefix sum over the previous row. This converts the transition into a constant-time range query: dp[i][j] = prefix[j] - prefix[j-i] (when j ≥ i). While iterating through j, maintain cumulative sums to build the next row efficiently. This removes the inner loop and reduces complexity to O(n*k). The technique is a classic optimization in dynamic programming where range-sum transitions are replaced with prefix sums. Modular arithmetic ensures values stay within limits.

This DP effectively models how permutations grow as the largest element is inserted into smaller permutations. Instead of enumerating permutations, it counts configurations mathematically. The prefix-sum trick transforms a cubic-style transition into a linear one over k, which is necessary for constraints up to n = 1000.

Recommended for interviews: The optimized DP with prefix sums is the expected solution. Interviewers often accept the basic DP recurrence first because it shows you understand how inverse pairs change when inserting elements. The optimized O(n*k) version demonstrates stronger mastery of dynamic programming transitions and range-sum optimization techniques commonly used in combinatorics-style counting problems.

Approach 1: Dynamic Programming Approach

We use a two-dimensional dynamic programming array, where dp[i][j] represents the number of permutations of array {1, 2, ..., i} with exactly j inverse pairs. The transition is based on the idea that when we insert a new element into an existing permutation, it can create new inverse pairs from 0 up to i-1.

This solution initializes a DP table and iteratively fills it up using the recursive formula derived for permutation inverses. The modulo operation ensures that the values remain within bounds and computationally manageable.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n*k)
Space Complexity: O(n*k)

Try this approach in the editor →

Approach 2: Dynamic Programming + Prefix Sum

We define f[i][j] as the number of arrays of length i with j inverse pairs. Initially, f[0][0] = 1, and the rest f[i][j] = 0.

Next, we consider how to obtain f[i][j].

Assume the first i-1 numbers are already determined, and now we need to insert the number i. We discuss the cases of inserting i into each position:

  • If i is inserted into the 1st position, the number of inverse pairs increases by i-1, so f[i][j] += f[i-1][j-(i-1)].
  • If i is inserted into the 2nd position, the number of inverse pairs increases by i-2, so f[i][j] += f[i-1][j-(i-2)].
  • ...
  • If i is inserted into the (i-1)th position, the number of inverse pairs increases by 1, so f[i][j] += f[i-1][j-1].
  • If i is inserted into the ith position, the number of inverse pairs does not change, so f[i][j] += f[i-1][j].

Therefore, f[i][j] = sum_{k=1}^{i} f[i-1][j-(i-k)].

We notice that the calculation of f[i][j] actually involves prefix sums, so we can use prefix sums to optimize the calculation process. Moreover, since f[i][j] only depends on f[i-1][j], we can use a one-dimensional array to optimize the space complexity.

The time complexity is O(n times k), and the space complexity is O(k). Here, n and k are the array length and the number of inverse pairs, respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

Time Complexity: O(n*k)
Space Complexity: O(n*k)

Dynamic Programming + Prefix Sum—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming (Naive Transition)O(n*k*n)O(n*k)Useful for understanding how inserting the largest element affects inverse pairs
Dynamic Programming with Prefix Sum OptimizationO(n*k)O(n*k)Best general solution for large constraints and interview settings

Video Solution

K Inverse Pairs Array - Leetcode 629 - Python • NeetCodeIO • 19,174 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is K Inverse Pairs Array easy or hard?
LeetCode classifies K Inverse Pairs Array as a Hard problem. The challenge comes from deriving the DP recurrence and recognizing the prefix sum optimization required to reduce the complexity to O(n*k).
K Inverse Pairs Array Python/Java solution
Most implementations use the same DP recurrence with prefix sums. Python, Java, C++, JavaScript, and C# solutions maintain a DP table and compute each row using cumulative sums while applying modulo 1e9+7 to prevent overflow.
How to solve K Inverse Pairs Array in O(n*k)?
Use dynamic programming where dp[i][j] counts permutations of size i with j inverse pairs. Maintain prefix sums of the previous DP row so the transition dp[i][j] = prefix[j] - prefix[j-i] can be computed in constant time. This removes the inner loop and reduces complexity to O(n*k).
What is the best approach for K Inverse Pairs Array?
The most efficient method uses dynamic programming with prefix sum optimization. Define dp[i][j] as the number of permutations of size i with j inverse pairs. Using prefix sums allows each transition to be computed in constant time, giving an overall complexity of O(n*k).
Is K Inverse Pairs Array asked at Google/Amazon/Meta?
Inverse pair counting and permutation DP problems appear in interviews at companies like Google and Amazon. Variants focusing on counting permutations with constraints are common in algorithm-heavy interviews that test dynamic programming and combinatorics reasoning.
What data structure is used in K Inverse Pairs Array?
The core structure is a 2D dynamic programming table where rows represent the number of elements and columns represent inverse pair counts. Prefix sum arrays are used to optimize the DP transitions and avoid repeated range summations.
What is the time complexity of K Inverse Pairs Array?
The optimized dynamic programming solution runs in O(n*k) time and O(n*k) space. A straightforward DP transition without optimization takes O(n*k*n) time because it sums up to i previous states for every dp[i][j].

Ready to solve this problem?

Practice K Inverse Pairs Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count the Number of Inversions