Number of Unequal Triplets in Array

To solve this problem, you can utilize a nested loop structure. The outer loop iterates over the first index of the triplet (i), the middle loop iterates over the second index (j), and the inner loop iterates over the third index (k). Within the innermost loop, you need to check if the elements at the three indices are distinct. If they are, increment the count.

Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def unequalTriplets(self, nums: List[int]) -> int:
        # Initialize the count
        count = 0

        # Iterate over the first index
        for i in range(len(nums) - 2):

            # Iterate over the second index
            for j in range(i + 1, len(nums) - 1):

                # Iterate over the third index
                for k in range(j + 1, len(nums)):

                    # Check if the elements are distinct
                    if nums[i] != nums[j] and nums[i] != nums[k] and nums[j] != nums[k]:
                        # If they are, increment the count
                        count += 1

        # Return the count
        return count

This solution has a time complexity of O(n^3) because there are three nested loops. This might not be the most efficient solution for large arrays, but it is simple and straightforward to understand.

Q&A

First, we count numbers using a hash map m.

For numbers a, b and c, we can form m[a] * m[b] * m[c] unique triplets.

Say we have 26 numbers (a…z). Number n forms these number of triplets:

m[a] * m[n] * m[o] + … + m[a] * m[n] * m[z] + m[b] * m[n] * m[o] + … + m[b] * m[n] * m[z] + … m[m] * m[n] * m[o] + … + m[m] * m[n] * m[z]. This formula can be simplified as sum(m[a]…m[m]) * m[n] * sum(m[o]…m[z]).

We can track sum on the left and right of m[n] as we go.

What about 0 <= i < j < k condition? Actually, the relation does not matter. What matters is that [i, j, k], [i, k, j], [k, i, j] and [k, j, i] represent the same triplet, so it should only be counted once.

Imagine you have a bag of colored balls. Each ball is labeled with a number and there can be multiple balls with the same number. You want to count how many unique combinations of three balls you can pull out of the bag, but only if all three balls have different numbers on them.

The algorithm starts by counting how many balls there are of each number. This is similar to sorting the balls by their labels and putting them into different buckets. The buckets are our hash map m, where the key is the number on the ball, and the value is the count of balls with that number.

Next, the algorithm works its way through the buckets one by one. For each bucket, it looks at all the balls in the buckets to its left (those with smaller numbers), and all the balls in the buckets to its right (those with larger numbers). For each such pair of left and right bucket, it can form one unique triplet with the current bucket.

The total number of unique triplets with the current bucket is the product of the count of balls in the current bucket, the total count of balls in the left buckets, and the total count of balls in the right buckets. This is summed up over all buckets to give the total number of unique triplets.

The algorithm uses two running sums, left and right, to keep track of the total count of balls in the buckets to the left and right of the current bucket, respectively.

The condition 0 <= i < j < k ensures that each triplet is counted only once. This condition is automatically satisfied by the algorithm’s way of progressing from left to right through the buckets. Each triplet corresponds to a unique ordering of three different numbers, and the algorithm guarantees that it will count each such ordering exactly once.

Lets say we have 4 kinds of numbers in m, denote them as a, b, c, d, and their frequency m[a], m[b], m[c], m[d] What we want to find is

m[a] * m[b] * m[c] m[a] * m[b] * m[d] m[a] * m[c] * m[d] m[b] * m[c] * m[d]

Actually, there are nC3 kinds of combinations we have to consider. If you look closer, the above combinations can be reduce as

   left             cnt           right

(0) * m[a] * (m[b] + m[c] + m[d]) (m[a]) * m[b] * (m[c] + m[d]) (m[a] + m[b]) * m[c] * (m[d]) (m[a] + m[b] + m[c]) * m[d] * (0)

Which is what we want.

Consider we have four kinds of numbers labeled as a, b, c, and d. The frequency of these numbers (how many times they appear) is represented by m[a], m[b], m[c], m[d] respectively.

We are interested in finding out how many unique triplets we can form from these numbers, given they must all be different.

Let’s look at all the possible triplets:

One triplet is made up of a, b, and c. The number of such triplets will be the product of the frequencies of a, b, and c: m[a] * m[b] * m[c].
Similarly, we can form m[a] * m[b] * m[d] triplets of a, b, and d.
Continuing in this way, we get m[a] * m[c] * m[d] triplets of a, c, and d, and m[b] * m[c] * m[d] triplets of b, c, and d.

But if you notice, you can also express the total number of triplets in a different, simpler way:

Start with the frequency of ‘a’. There are no numbers to the left of ‘a’ (left = 0), and all the remaining numbers are to the right of ‘a’ (right = m[b] + m[c] + m[d]). So, we get (0) * m[a] * (m[b] + m[c] + m[d]) triplets with ‘a’.
Then move to ‘b’. Now, ‘a’ is to the left of ‘b’, and ‘c’ and ’d’ are to its right. So, we get (m[a]) * m[b] * (m[c] + m[d]) triplets with ‘b’.
Next is ‘c’, with ‘a’ and ‘b’ to its left and ’d’ to its right. This gives (m[a] + m[b]) * m[c] * (m[d]) triplets with ‘c’.
Finally, for ’d’, all the other numbers are to its left, and there are no numbers to its right. So, we get (m[a] + m[b] + m[c]) * m[d] * (0) triplets with ’d’.

If you add up all these, you get the total number of triplets. And this is exactly what the algorithm does, with ’left’ representing the total frequency of numbers to the left of the current number, and ‘right’ representing the total frequency of numbers to its right.