Number of Unequal Triplets in Array

Number of Unequal Triplets in Array

What is this problem about?

The Number of Unequal Triplets in Array problem asks you to count triplets (i, j, k) where i < j < k and arr[i] != arr[j], arr[j] != arr[k], and arr[i] != arr[k] — all three elements are distinct. This easy coding problem uses frequency counting with a combinatorial formula.

Why is this asked in interviews?

Paytm asks this easy problem to test the ability to count valid triplets efficiently using group frequency products rather than brute-force O(n³). The array, hash table, and sorting interview pattern is applied through the frequency-based combinatorial insight.

Algorithmic pattern used

Frequency count + ordered group product. Count the frequency of each unique value. Enumerate all unique triplets of distinct values (a, b, c) and multiply their frequencies to get the number of valid ordered triplets. But ordering the groups while counting avoids permutation issues. Better: for each "middle" value group of size m with left elements before it (different values) and right elements after it (different values), add left * m * right. Compute left/right cumulatively.

Example explanation

arr=[4,4,2,4,3,2,5]. Frequencies: {4:3, 2:2, 3:1, 5:1}. Order groups: left=0, current=3(4s), right=4(2,3,5).

• Group {4}: left=0. Contribution=034=0.
• Group {2}: left=3. Contribution=322=12. right=2(3,5).
• Group {3}: left=5. Contribution=511=5. right=1(5).
• Group {5}: left=6. Contribution=610=0. Total = 0+12+5+0 = 17.

Common mistakes candidates make

• Using O(n³) brute force (checking all triplets).
• Not recognizing that order matters — choosing (a,b,c) and (c,b,a) are different index orders but can yield the same value triple; frequency approach handles this.
• Forgetting to account for multiple elements of the same value (use frequency, not just group count).
• Off-by-one in cumulative left/right counts.

Interview preparation tip

Triplet counting with frequency groups uses the "fix the middle element" technique: for each group as the middle, multiply elements before × group size × elements after. This generalizes to counting triplets with other constraints. Practice "count triplets with i < j < k and all different" variants. The key is avoiding O(n³) by leveraging group structure and cumulative counts.