Posted on 2019-06-17.

The Count Triplets problem can be solved efficiently using hashtables and careful analysis. This post first shows a brute force solution, then explains the more efficient approach. My solutions are written in Kotlin. I show my implementations of the countTriplets function; for the main method, I’m using the template that HackerRank provides.

If you just want hints, without the full solution, see: June KC Code Challenge Hints.

Solutions:

• Brute Force: O(N³)
• Single Pass: O(N)

Brute Force

It’s important to notice that the problem statement says we’re only interested in triplets of indices (i, j, k) where i < j < k. A triplet consisting of, for example, the second element of the array, the first element, and the third element, would not be counted, though a triplet consisting of the first, second, and third elements might be.

A simple but extremely inefficient approach would be to loop through every possible triplet and check whether it meets the necessary condition:

fun countTriplets(arr: Array<Long>, r: Long): Long {
    var total = 0L

    for (i in 0 until arr.size) {
        for (j in (i + 1) until arr.size) {
            for (k in (j + 1) until arr.size) {
                if (arr[i] * r == arr[j] && arr[j] * r == arr[k]) {
                    total++
                }
            }
        }
    }

    return total
}

The outer loop will run N times, the first-level inner loop will run almost N times for each of the outer loop’s iterations, and the innermost loop will run almost N times for each of the first-level inner loop’s iterations. So the overall time complexity is O(N³). No new storage is allocated, so the space complexity is O(1) (excluding the input array).

Some of the HackerRank test cases give you an array of size 100000, which means the inner loop would have to execute 100000³ = 1 quadrillion times. That will take far too long.

Single Pass

To clarify the following discussion, let’s define some terms.

A triplet (i, j, k) could also be called a 3-tuple; we’ll also discuss 2-tuples like (i, j) and 1-tuples like (i).

We’ll call a tuple an answer tuple if it meets the following two conditions set by the problem:

1. i < j, j < k, etc.
2. a[j] = a[i] * r, a[k] = a[j] * r, etc.

We can solve the Count Triplets problem with O(N) time and space complexity. To figure out how, let’s start with a simpler problem and work our way up. We can first think about how we’d find the number of 1-tuples, then how we’d find the number of 2-tuples, and finally the number of 3-tuples. (In fact, the solution discussed here works just as well for tuples of any length; for a K-tuple, the time complexity is O(K * N).)

Let’s consider how we’d find all the answer 1-tuples for the following test input:

4 2
1 2 2 4

A 1-tuple contains just a single element (i). This means all 1-tuples meet the conditions specified above. So the number of answer 1-tuples is just equal to the number of elements in the input array, 4.

What about finding answer 2-tuples (aka pairs) in that input?

Answer 2-tuples must meet these conditions:

1. i < j
2. a[j] = a[i] * r

In the example above, there are 4 answer 2-tuples. For (0, 1) and (0, 2), a[i] = 1 and a[j] = 2, so those both work since 1 * 2 = 2. And for (1, 3) and (2, 3), a[i] = 2 and a[j] = 4, so those both work since 2 * 2 = 4.

Notice that for any particular value of a[j], then (for a given ratio) there’s only one possible value that could be a[i] that would form an answer 2-tuple: a[j] / r. If we know how many indices in the array contain that value, then we know how many answer 2-tuples there are for this j value. To be able to answer that quickly, all we have to do is maintain a hashtable as we go through the array, mapping each number to the count of times we’ve seen that number so far.

So, we can find the count of answer 2-tuples with a single pass through the array; the algorithm is:

1. Create an empty hashtable L1 to hold number counts.
2. Start with a total of 0.
3. For each index j in the input array:
   1. Increment total by L1[a[j] / r] to record any answer 2-tuples we found.
   2. Increment L1[a[j]] by 1 to record the number we found.

Now, what about 3-tuples?

Answer 3-tuples must meet these conditions:

1. i < j
2. a[j] = a[i] * r
3. j < k
4. a[k] = a[j] * r

Notice that the first two conditions are the same as for answer 2-tuples. As with answer 2-tuples, for any particular value of a[j], there’s only one allowable value for a[i]; similarly, for any particular value of a[k], there’s only one allowable value for a[j].

So, we could rewrite the conditions for being an answer 3-tuple as follows:

1. Meets the qualifications of an answer 2-tuple.
2. j < k
3. a[k] = a[j] * r

In the example above, there are 2 answer 3-tuples. (0, 1, 3) and (0, 2, 3) both meet the first condition since we already established that (0, 1) and (0, 2) were answer 2-tuples; and for both, a[j] = 2 and a[k] = 4, so a[j] * 2 = a[k].

To find out how many answer 3-tuples there are for a given index k, we just need to know how many answer 2-tuples there are for j < k where a[j] = a[k] / r. The algorithm above could easily generate that information; all we need to do is save the count of answer 2-tuples per value into a hashtable as we go along, instead of summing them into a single total.

So, the algorithm for finding all the answer 3-tuples is:

1. Create an empty hashtable for number counts.
2. Create an empty hashtable for answer 2-tuple counts.
3. Start with a total of 0.
4. For each index k in the input array:
   1. Increment total by L2[a[k] / r] to record any answer 3-tuples we found.
   2. Increment L2[a[k]] by L1[a[k] / r] to record any answer 2-tuples we found.
   3. Increment L1[a[k]] by 1 to record the number we found.

To generalize this to tuples of length K, we can maintain K hashtables (L1, L2, L3, … LK), and update all of them each time we process an element of the input array. At the end, the overall answer will just be the sum of the values in the last hashtable.

Here’s a walkthrough of applying such an algorithm to the example given above. L1, L2, and L3 are the hashtables containing counts of solution 1-tuples, 2-tuples, and 3-tuples respectively.

Note that in each step, when calculating L2 you need to use the last step’s L1, and for L3 you need the last step’s L2, etc. So your code needs to update L3, then L2, then L1, in that order.

The code below is written to support arbitrary tuple length - you’d just change the 3 parameter in the call to combinationsByNumByLen:

fun countGeometricProgressions(arr: Array<Long>, r: Long, len: Int): Long {
    val combinationsByNumByLen = Array(len) { mutableMapOf<Long, Long>() }

    for (n in arr) {
        if (n % r == 0L) {
            for (i in (len - 2) downTo 0) {
                val combinations = combinationsByNumByLen[i][n / r] ?: 0
                if (combinations > 0) {
                    combinationsByNumByLen[i + 1][n] = (combinationsByNumByLen[i + 1][n] ?: 0) + combinations
                }
            }
        }

        combinationsByNumByLen[0][n] = (combinationsByNumByLen[0][n] ?: 0) + 1
    }

    return combinationsByNumByLen.last().values.sum()
}

fun countTriplets(arr: Array<Long>, r: Long) = countGeometricProgressions(arr, r, 3)