Given a series of n numbers, I need an algorithm that runs in worst case O(n*k) to figure out how many arrangements of those n numbers will give me a score of exactly k.

Note that the series does not contain duplicate elements.

The score of a series of numbers is calculated by the number of smaller numbers an element in the series has before it.

For example, The score of the below series would be:

series = [5,3,6]

5 has no smaller number before it, so 0

3 has no smaller number before it, so 0

6 has 2 smaller numbers before it (5,3) so 2

Adding all of this, we get a total score for the series as 2.

What I have tried to do:

I have tried to find all possible arrangements of the series -> (n! many arrangements)

and count the ones that have a score of k.

But this has a worst case time complexity of O(n!). Any help/ideas will be much appreciated. Thanks!

  • $\begingroup$ Are numbers all different or could there be duplicates? $\endgroup$
    – Nathaniel
    Commented Nov 8, 2022 at 13:16
  • $\begingroup$ @Nathaniel No duplicates, all different $\endgroup$ Commented Nov 8, 2022 at 13:18
  • $\begingroup$ As the numbers are all different you are counting permutations with k inversions. $\endgroup$ Commented Nov 8, 2022 at 17:15

1 Answer 1


Note that the values contained in the series are not important, and you can consider those values are exactly $1, 2, …, n$ (because only relative order is important).

Denote $A(n, k)$ the number of arrangements of $n$ values to reach score $k$.

Given an arrangement of $n$ values of score $k$, if you add the value $n+1$, you can:

  • put it in first position and not change the score;
  • put it in second position and add one to the score;
  • put it in last position and add $n$ to the score.

Considering all this, we get the induction formula: $$A(n+1, k) = \sum\limits_{i = 0}^n A(n, k - i)$$ The base cases are:

  • $A(1, 0) = 1$;
  • $A(n, k) = 0$ if $k < 0$.

The total runtime of dynamic programming algorithm computing this would be $\mathcal{O}(n^2k) = \mathcal{O}(n^2)$ if $k$ is considered a constant.

There may be a closed formula that could be used to compute this in $\mathcal{O}(1)$, but I don't know it.

  • $\begingroup$ is there a way to do this in O(n*k) time? $\endgroup$ Commented Nov 9, 2022 at 0:21
  • $\begingroup$ @brownturtle, Given $A(n,0), \ldots, A(n,k)$, you can compute $A(n+1,0), \ldots, A(n+1, k)$ in $O(k)$ time based on the recurrent expression in the post (it's a simple exercise, one way is to do some preprocessing on $A(n,0), \ldots, A(n,k)$). Also, from this recurrence, you can derive another recurrence of the form $A(n+1,k+1) = A(n+1,k) + \ldots$, which also makes it clear how to get $O(k)$ time. $\endgroup$
    – Dmitry
    Commented Nov 9, 2022 at 1:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.