Leetcode.com problem 629: "K Inverse Pairs"

James S. Plank

Sun Jul 17 16:22:45 EDT 2022

This was classified as a hard problem.

Problem Statement.
A skeleton with a main() that reads problems from stdin.
tests.sh -- Testing script.
answers.txt -- Correct output of the testing script.
permutation.cpp -- A solution that I knew was too slow, but it gave me correct answers that I could use to test my other programs.
too-slow.cpp -- A dynamic program which ends up being O(n²k), which is too slow, but you can use it to figure out the faster solution.
solution.cpp -- The faster solution.
Success Rate (as of July, 2022): 42.7%

In case Leetcode's servers are down

If Leetcode's servers are down, I've given you tools to do the problem anyway. Do the solution in main.cpp, and then you can test yourself with tests.sh. Your output should match answers.txt, and your timing should be roughly the same as mine, which was just under 2 seconds.

Here is a summary of the problem:

You are given two integers, n and k, each between 1 and 1000.
Given a vector v of integers, and "inverse pair" is a pair of indices, i and j such that i < j and v[i] > v[j].
Consider all of the permutations of the numbers from 1 to n. Return the number of permutations that contain exactly k inverse pairs.
Return your result mod 1,000,000,007.

The examples

#1: n = 3, k = 0.  The answer is 1 -- only the permutation (1,2,3) has no inverse pairs.
#2: n = 3, k = 1.  The answer is 2.  The permutations (1,3,2) and (2,1,3) have exactly one inverse pair.

Hints

I solved this in three stages. In the first, I wrote a program that I knew was too slow, but I could use to verify other programs. In this first program, I enumerated the permutations of the numbers from 0 to n-1, and for each permutation, I counted the inverse pairs.

The program is in permutation.cpp and I assume you can write it quickly -- use the C++ routine next_permutation(). It gets slow when n gets to 10.

UNIX> g++ permutation.cpp 
UNIX> echo 7 7 | ./a.out
359
UNIX> echo 8 8 | ./a.out
1415
UNIX> echo 9 9 | ./a.out
5545
UNIX> echo 10 10 | ./a.out      # This one takes over a second
21670
UNIX>

Spot the recursion - A DP solution that is too slow

This sure feels like a dynamic programming problem, so let's play "spot the recursion." I focused on the vector 0, 1, 2, ..., n-1, and the first element -- the zero. Now, suppose I affix it as the first element. Then, the number of answers will be the same as when n is n-1 and k is unchanged.

Let's take example 2 as an example. The vector is 0, 1, 2. If I don't move the zero, then the answer is the same as when n=2 and k=1: It is one.

Now, suppose we move the 0 to index 1, so that the vector is 1, 0, 2, ..., n-1. Now there is one inverse pair -- 0 and 1, and so long as the 0 is in index 1, it doesn't matter what we do with the rest of the elements -- the 0 will be part of exactly one inverse pair -- with whatever element is in index 0. So let's delete the 0. The answer is going to be the same as when n is n-1 and k is k-1.

Again, let's take example 2 as an example: the vector is 0, 1, 2. If we move the 0 to index 1, so that the vector is 1, 0, 2, then the number of permutations is the same as when n is 2, and k is zero: It is one.

Continuing, suppose we move the 0 to index 2, so that the vector is 1, 2, 0, 3, ..., n-1. Now the answer is the same as when n is n-1 and k is k-2.

See the pattern? Let's call the problem knp(n,k). You can prove to yourself that the answer is:

The sum of knp(n-1,k-i) for i going from 0 to min(k,n-1).

Go ahead and program this up -- it's pretty straightforward. While you're at it, add a memoization cache on n and k. I have this solution in too-slow.cpp. We can run it on the same examples as we did with permutation.cppbefore:

UNIX> g++ too-slow.cpp
UNIX> echo 7 7 | ./a.out
359
UNIX> echo 8 8 | ./a.out
1415
UNIX> echo 9 9 | ./a.out
5545
UNIX> echo 10 10 | ./a.out
21670
UNIX>

It's much faster, too. However, before you submit that solution to Leetcode, you should test the hardest values of n and k:

UNIX> time echo 1000 1000 | ./a.out
663677020

real	0m5.343s
user	0m5.331s
sys	0m0.007s
UNIX>

Crap. Glad I did that before submitting, but now we have to think harder.

Examining the recursive calls to make a faster solution

I was irritated that the previous solution didn't work, but if you examine what's going on, you'll see that you can do O(n) work in each recursive call. Since the number of calls is roughly O(nk), you're left with O(n²k), and with n and k being as high as 1000, you can see why it's too slow.

So, let's take a look at the recursive calls and see if we can spot a better recursion. Let's examine what we do when we call knp(4,12). As it turns out, we make the following calls:

knp(3,12)
knp(3,11)
knp(3,10)
knp(3,9)

Now, what recursive calls do we make when we call knp(4,11). It's the following:

knp(3,11)
knp(3,10)
knp(3,9)
knp(3,8)

This gives us a new recursion: knp(4,12) = knp(4,11) + knp(3,12) - knp(3,8). Instead of making min(n,k) recursive calls, we're making three! Can you use this information to craft a faster solution? You'll have to handle the cases where k > n and k ≤ n differently. Use an example like the one above to figure it out.

My solution is in solution.cpp. The runtime was faster than 12.18% of C++ submissions and the memory usage was less than 21.15% of C++ submissions, which isn't exactly stomping the field, but who cares -- it's fast enough to be accepted!