LeetCode 2475 - Number of Unequal Triplets in Array

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Sorting

Solution

Problem Understanding

The problem gives us a 0-indexed integer array nums, and we must count how many triplets (i, j, k) satisfy two conditions.

First, the indices must be strictly increasing:

0 <= i < j < k < nums.length

Second, the values at those indices must all be different from each other:

nums[i] != nums[j]
nums[i] != nums[k]
nums[j] != nums[k]

This means we are looking for triplets of positions where the three selected numbers are pairwise distinct.

The input array contains positive integers, and the array length is between 3 and 100. Since the maximum size is fairly small, even cubic solutions are technically acceptable because:

100^3 = 1,000,000

One million operations is manageable. However, the problem is still a good opportunity to think about how to reduce unnecessary work using counting and combinatorics.

The output is a single integer representing the total number of valid triplets.

One important detail is that the order of indices matters only in terms of increasing position. The triplet (0, 2, 4) is valid, but (2, 0, 4) is not because the indices are not strictly increasing.

Several edge cases are important to consider:

Arrays where all numbers are identical, because no valid triplets exist.
Arrays where all numbers are distinct, because every combination of three indices is valid.
Arrays with repeated groups of values, where we must carefully avoid overcounting.
Very small arrays of length 3, where there is only one possible triplet.

The constraints guarantee that the input always contains at least three elements, so we never need to handle arrays that are too short.

Approaches

Brute Force Approach

The most direct solution is to try every possible triplet (i, j, k).

We use three nested loops:

The first loop chooses index i
The second loop chooses index j
The third loop chooses index k

For each triplet, we check whether:

nums[i] != nums[j]
nums[i] != nums[k]
nums[j] != nums[k]

If all three conditions are true, we increment the answer.

This approach is correct because it explicitly examines every possible valid index combination and counts exactly the triplets that satisfy the conditions.

However, the time complexity is:

O(n^3)

because we examine every triplet.

Although this passes within the problem constraints, it performs unnecessary repeated comparisons.

Optimal Approach

The key observation is that we do not actually care about the positions individually. What matters is how many times each distinct value appears.

Suppose we know the frequency of every number.

If we process the distinct values one by one, we can treat each value as the "middle group" of a triplet.

For a particular value with frequency count:

left represents how many elements belong to smaller processed groups
right represents how many elements remain in unprocessed groups

Then the number of triplets using this value group is:

left * count * right

Why does this work?

We choose one element from the left side
One element from the current value group
One element from the right side

Since all three groups represent different values, every constructed triplet automatically contains distinct numbers.

This converts the problem from checking individual triplets into counting combinations between frequency groups.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Checks every possible triplet directly
Optimal	O(n)	O(n)	Uses frequency counting and combinatorial counting

Algorithm Walkthrough

Optimal Frequency Counting Algorithm

First, count how many times each number appears in the array.

We use a hash map where:

Key = number
Value = frequency of that number

For example:

nums = [4,4,2,4,3]

produces:

{
    4: 3,
    2: 1,
    3: 1
}

Initialize three variables:

left = 0
right = len(nums)
answer = 0

Here:

left tracks how many elements belong to already processed value groups
right tracks how many elements remain unprocessed

Iterate through each frequency in the hash map.

For each frequency count:

Remove the current group from right
Compute how many triplets use this group as the middle group
Add the result to the answer
Add the current group into left

The formula used is:

answer += left * count * right

This works because:

left choices come from previously processed distinct values
count choices come from the current value
right choices come from future distinct values

Continue until all frequency groups are processed.
Return the final answer.

Why it works

The algorithm partitions the array into groups of equal values. Every valid triplet must select elements from three different groups.

When processing one frequency group:

left contains all elements from earlier distinct groups
count contains all elements from the current distinct group
right contains all elements from later distinct groups

Multiplying these counts gives the exact number of unique triplets using those three regions. Since every triplet belongs to exactly one such partitioning, every valid triplet is counted exactly once.

Python Solution

from collections import Counter
from typing import List

class Solution:
    def unequalTriplets(self, nums: List[int]) -> int:
        frequency = Counter(nums)

        left = 0
        right = len(nums)
        answer = 0

        for count in frequency.values():
            right -= count

            answer += left * count * right

            left += count

        return answer

The implementation begins by building a frequency map using Counter. This allows us to quickly determine how many times each distinct value appears.

The variable right initially contains the total number of elements in the array. As we process each frequency group, we subtract its count from right because those elements are no longer considered part of the future groups.

The formula:

answer += left * count * right

computes how many valid triplets can be formed using:

one element from previously processed groups,
one element from the current group,
one element from future groups.

Finally, we add the current frequency into left so future iterations can use it.

The implementation is compact because the combinatorial insight eliminates the need for nested loops.

Go Solution

package main

func unequalTriplets(nums []int) int {
	frequency := make(map[int]int)

	for _, num := range nums {
		frequency[num]++
	}

	left := 0
	right := len(nums)
	answer := 0

	for _, count := range frequency {
		right -= count

		answer += left * count * right

		left += count
	}

	return answer
}

The Go implementation follows the same logic as the Python version.

A map[int]int is used to store frequencies. Go maps iterate in arbitrary order, but this does not matter because the counting formula works for any ordering of distinct groups.

Go integers are sufficient because the maximum number of triplets is small under the given constraints.

Worked Examples

Example 1

nums = [4,4,2,4,3]

Step 1: Build Frequency Map

Value	Frequency
4	3
2	1
3	1

Step 2: Initialize Variables

Variable	Value
left	0
right	5
answer	0

Step 3: Process Frequency Groups

Suppose iteration order is:

4 -> 2 -> 3

Process value 4, count = 3

Update right:

right = 5 - 3 = 2

Compute contribution:

answer += 0 * 3 * 2 = 0

Update left:

left = 0 + 3 = 3

left	right	answer
3	2	0

Process value 2, count = 1

Update right:

right = 2 - 1 = 1

Compute contribution:

answer += 3 * 1 * 1 = 3

Update left:

left = 3 + 1 = 4

left	right	answer
4	1	3

Process value 3, count = 1

Update right:

right = 1 - 1 = 0

Compute contribution:

answer += 4 * 1 * 0 = 0

Final answer:

Example 2

nums = [1,1,1,1,1]

Step 1: Frequency Map

Value	Frequency
1	5

Step 2: Initialize

Variable	Value
left	0
right	5
answer	0

Step 3: Process Group

Process value 1, count = 5

Update right:

right = 0

Contribution:

answer += 0 * 5 * 0 = 0

Final answer:

No valid triplets exist because all numbers are identical.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Building the frequency map and iterating through frequencies are both linear
Space	O(n)	The hash map may store up to n distinct values

The algorithm processes each element once while building the frequency map. After that, it iterates through the distinct values exactly once.

Although the brute-force solution is acceptable for n <= 100, the frequency-based solution is asymptotically more efficient and demonstrates stronger algorithmic reasoning.

Test Cases

from typing import List
from collections import Counter

class Solution:
    def unequalTriplets(self, nums: List[int]) -> int:
        frequency = Counter(nums)

        left = 0
        right = len(nums)
        answer = 0

        for count in frequency.values():
            right -= count
            answer += left * count * right
            left += count

        return answer

solution = Solution()

assert solution.unequalTriplets([4, 4, 2, 4, 3]) == 3  # provided example
assert solution.unequalTriplets([1, 1, 1, 1, 1]) == 0  # all identical
assert solution.unequalTriplets([1, 2, 3]) == 1  # smallest valid distinct case
assert solution.unequalTriplets([1, 2, 3, 4]) == 4  # all triplets valid
assert solution.unequalTriplets([1, 1, 2, 2, 3, 3]) == 8  # repeated groups
assert solution.unequalTriplets([1, 2, 2, 3]) == 2  # one duplicated value
assert solution.unequalTriplets([5, 5, 5, 6, 7]) == 3  # one large duplicate group
assert solution.unequalTriplets([1, 2, 1, 2, 1, 2]) == 0  # only two distinct values
assert solution.unequalTriplets([10, 20, 30, 40, 50]) == 10  # all distinct larger case
assert solution.unequalTriplets([1, 1, 2, 3, 4]) == 7  # mix of duplicates and distinct

Test	Why
`[4,4,2,4,3]`	Validates the provided example
`[1,1,1,1,1]`	Ensures identical values produce zero
`[1,2,3]`	Smallest array with one valid triplet
`[1,2,3,4]`	Every triplet should be valid
`[1,1,2,2,3,3]`	Tests balanced duplicate groups
`[1,2,2,3]`	Tests partial duplication
`[5,5,5,6,7]`	Tests heavy skew toward one value
`[1,2,1,2,1,2]`	Only two distinct values exist
`[10,20,30,40,50]`	Larger all-distinct scenario
`[1,1,2,3,4]`	Mixed duplicates and unique values

Edge Cases

One important edge case occurs when all numbers are identical. For example:

[1,1,1,1]

A naive implementation might accidentally count triplets if it only checks partial distinctness conditions. Our implementation handles this correctly because the frequency map contains only one group, so either left or right is always zero, making every contribution zero.

Another important case is when all numbers are distinct. For example:

[1,2,3,4]

In this scenario, every possible triplet is valid. The algorithm naturally computes the correct combinatorial total because every frequency is 1, so the formula effectively counts all combinations of three distinct positions.

A third important edge case is when there are only two distinct values in the entire array. For example:

[1,1,2,2]

No valid triplet can exist because every triplet would necessarily repeat one of the two values. The implementation handles this automatically because the multiplication formula requires three separate groups to contribute nonzero values.

Another subtle case involves uneven frequency distributions such as:

[5,5,5,5,6,7]

It is easy to accidentally undercount or overcount when one value appears many times. The formula correctly accounts for multiplicity because selecting one of the four 5s creates four distinct valid index combinations.