Number of Unequal Triplets in Array - Video Solutions

Problem Overview: Given an integer array nums, count the number of index triplets (i, j, k) such that i < j < k and the values nums[i], nums[j], and nums[k] are all different. The task is to efficiently count all valid combinations without checking unnecessary duplicates.

Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)

Check every possible triplet of indices using three nested loops. For each combination (i, j, k), verify that nums[i] != nums[j], nums[i] != nums[k], and nums[j] != nums[k]. If all three values differ, increment the count. This approach directly follows the problem definition and is easy to implement, but the O(n^3) time complexity becomes slow as the array grows. It’s mainly useful as a baseline or for demonstrating correctness before optimization.

Approach 2: Frequency Counting with HashMap (O(n + k) time, O(k) space)

Instead of checking every index triplet, count how many times each value appears using a hash table. Suppose a value appears freq times. Maintain two running counts: elements to the left (left) and elements to the right (right). For each distinct value, the number of triplets where it is the middle group is left * freq * right. Update left as you iterate through unique values and recompute right = n - left - freq. This avoids iterating over indices and instead counts valid combinations using frequencies. The algorithm runs in O(n + k) time where k is the number of distinct values.

Alternative: Sorting + Group Counting (O(n log n) time, O(1) extra space)

Another option is sorting the array first using a standard sorting algorithm. After sorting, identical values appear in contiguous blocks. Compute the size of each block and apply the same combinational idea used in the hash map approach: elements before the block form the left group and elements after form the right group. Sorting introduces O(n log n) time but removes the need for a hash map.

Recommended for interviews: The frequency counting solution using a Hash Table is the expected answer. It reduces the problem from checking index combinations to counting value groups. Mentioning the brute force approach first shows you understand the definition of the triplet constraint, while the optimized counting approach demonstrates strong algorithmic thinking with array frequency analysis.