Leetcode 2475. Number of Unequal Triplets in Array

Let's understand what we're being asked to do. We have an array like [1, 3, 5, 7, 9] and need to count how many triplets (i, j, k) exist where i < j < k and all three values are pairwise distinct (meaning arr[i], arr[j], and arr[k] are all different from each other).

Tracing through: Consider indices (0, 1, 2) with values (1, 3, 5) - all distinct, so this counts! Consider (0, 1, 3) with values (1, 3, 7) - all distinct, counts! But if we had [1, 3, 3, 7], then (0, 1, 2) would give values (1, 3, 3) - NOT all distinct, so this wouldn't count.

Important constraint: With n ≤ 100, we have at most 100 elements. This means we could check all possible triplets (there are at most 100 * 99 * 98 / 6 combinations), but there's a smarter way using frequency counting.

Edge cases to consider: What if the array has fewer than 3 elements? (return 0). What if all elements are the same? (return 0). What if all elements are distinct? (return the number of ways to choose 3 from n).

The straightforward approach uses three nested loops to check every possible triplet (i, j, k) where i < j < k. For each triplet, verify that all three values nums[i], nums[j], and nums[k] are pairwise distinct by comparing them. If all three are different, increment the count. This approach is simple to understand and implement but checks every combination individually without leveraging any patterns.

def count_distinct_triplets(nums):
    """
    Count triplets (i, j, k) where i < j < k and nums[i], nums[j], nums[k] are pairwise distinct.
    Brute force approach: check all possible triplets.
    """
    n = len(nums)
    count = 0
    
    # Outer loop: iterate through all possible i positions
    for i in range(n):
        # Middle loop: iterate through all possible j positions (j > i)
        for j in range(i + 1, n):
            # Inner loop: iterate through all possible k positions (k > j)
            for k in range(j + 1, n):
                # Check if all three values are pairwise distinct
                if nums[i] != nums[j] and nums[j] != nums[k] and nums[i] != nums[k]:
                    count += 1
    
    return count

Instead of checking every possible triplet (i, j, k) individually, notice that the order of indices matters, but the order of values doesn't for counting distinct triplets.

If we have 3 copies of value 5, 2 copies of value 7, and 1 copy of value 9, we can count how many ways to pick one 5, one 7, and one 9 - that's 3 * 2 * 1 = 6 triplets with these three distinct values!

By grouping values by their frequency (how many times each appears), we transform the problem from checking O(n³) individual triplets into counting combinations based on frequencies.

For each set of 3 distinct values, if they appear f1, f2, and f3 times respectively, we can form f1 * f2 * f3 valid triplets. This is much faster than checking each triplet individually!

Think about choosing a team of 3 people from different departments:

• Department A has 4 people
• Department B has 3 people
• Department C has 2 people

How many ways can you pick one person from each department? It's 4 * 3 * 2 = 24 ways.

This is exactly our problem: each distinct value is a 'department', its frequency is how many 'people' are in it, and we need to pick one from each of three different departments.

The optimal approach uses frequency counting to avoid checking individual triplets. First, build a frequency map counting how many times each distinct value appears in the array. Then, iterate through all combinations of three distinct values from the frequency map. For each combination of three distinct values with frequencies f1, f2, and f3, add f1 * f2 * f3 to the result (this represents all valid triplets using these three values). This leverages the mathematical insight that the number of ways to pick one element from each of three groups is the product of their sizes.

def count_distinct_triplets(arr):
    """
    Count triplets (i<j<k) with pairwise distinct values using frequency counting.
    Optimal approach: O(n + m^3) where m is number of distinct values.
    """
    # Build frequency map
    freq = {}
    for num in arr:
        freq[num] = freq.get(num, 0) + 1
    
    # Get all distinct values
    distinct_values = list(freq.keys())
    count = 0
    
    # Iterate through all combinations of 3 distinct values
    for i in range(len(distinct_values)):
        for j in range(i + 1, len(distinct_values)):
            for k in range(j + 1, len(distinct_values)):
                # Multiply frequencies: f1 * f2 * f3
                val1 = distinct_values[i]
                val2 = distinct_values[j]
                val3 = distinct_values[k]
                count += freq[val1] * freq[val2] * freq[val3]
    
    return count

• Frequency map combinatorics: When counting triplets/pairs with constraints and n ≤ 100-500, convert from O(n³) index iteration to frequency-based counting - group identical values first, then use combinatorics (nC3, nC2) to count valid combinations without explicit loops.
• Three-partition counting technique: For pairwise distinct triplets, iterate through each unique value as the "middle" element and multiply left_count × middle_frequency × right_count where left contains all processed values and right contains unprocessed ones - this elegantly ensures all three values differ.
• HashMap frequency preprocessing: Build a frequency map first to transform the problem space from array indices to value counts - this reduces complexity when the constraint is about value distinctness rather than index relationships, especially when duplicate values exist.
• Avoid triple nested loops trap: The naive O(n³) solution checking all (i,j,k) combinations is tempting but wasteful - recognize that when order doesn't matter semantically (only values, not positions), you can collapse identical values and use mathematical counting instead of enumeration.
• Combinatorial counting optimization: Understanding that choosing 3 distinct values from frequencies f1, f2, f3 yields f1 × f2 × f3 combinations is crucial - this pattern extends to any k-tuple counting problem where you need distinct values from groups with repetitions.
• Real-world duplicate handling: This frequency-map approach mirrors real scenarios like counting unique product combinations in inventory systems, analyzing distinct user interaction patterns in analytics, or finding diverse team compositions from department rosters where duplicates exist.