pythoncounting

How to count triplets of i,j,k such that i < j < k


I want to know an efficient way of calculating the count of triplets i, j, and k such that i < j < k.

I've tried using the following code:

for i in range(n):
  for j in range(i + 1, n):
    for k in range(j + 1, n):
      ans += 1

But that would result in O(N3) time complexity and that is not very efficient. O(N log N) time complexity (or faster) would be optimal.


Solution

  • You don't need any loops. There is a closed form formula for this:

    1/6 n(n**2 - 3n + 2)

    Or:

    1/6 (n - 2)(n - 1)n