# 2475. Number of Unequal Triplets in Array

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 // Assume that we have 4 kinds of numbers a, b, c, and d in the count map. // // What we want is: // cnt[a] * cnt[b] * cnt[c] // cnt[a] * cnt[b] * cnt[d] // cnt[a] * cnt[c] * cnt[d] // cnt[b] * cnt[c] * cnt[d] // // The above combinations can be reduced as: // // prev | curr | next // ---------------------------------------------------------------- // (0) * cnt[a] * (cnt[b] + cnt[c] + cnt[d]) // (cnt[a]) * cnt[b] * (cnt[c] + cnt[d]) // (cnt[a] + cnt[b]) * cnt[c] * (cnt[d]) // (cnt[a] + cnt[b] + cnt[c]) * cnt[d] * (0) class Solution { public: int unequalTriplets(vector& nums) { int ans = 0; int prev = 0; int next = nums.size(); unordered_map count; for (const int num : nums) ++count[num]; for (const auto& [_, freq] : count) { next -= freq; ans += prev * freq * next; prev += freq; } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 // Assume that we have 4 kinds of numbers a, b, c, and d in the count map. // // What we want is: // cnt[a] * cnt[b] * cnt[c] // cnt[a] * cnt[b] * cnt[d] // cnt[a] * cnt[c] * cnt[d] // cnt[b] * cnt[c] * cnt[d] // // The above combinations can be reduced as: // // prev | curr | next // ---------------------------------------------------------------- // (0) * cnt[a] * (cnt[b] + cnt[c] + cnt[d]) // (cnt[a]) * cnt[b] * (cnt[c] + cnt[d]) // (cnt[a] + cnt[b]) * cnt[c] * (cnt[d]) // (cnt[a] + cnt[b] + cnt[c]) * cnt[d] * (0) class Solution { public int unequalTriplets(int[] nums) { int ans = 0; int prev = 0; int next = nums.length; Map count = new HashMap<>(); for (final int num : nums) count.merge(num, 1, Integer::sum); for (final int freq : count.values()) { next -= freq; ans += prev * freq * next; prev += freq; } return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 # Assume that we have 4 kinds of numbers a, b, c, and d in the count map. # # What we want is: # cnt[a] * cnt[b] * cnt[c] # cnt[a] * cnt[b] * cnt[d] # cnt[a] * cnt[c] * cnt[d] # cnt[b] * cnt[c] * cnt[d] # # The above combinations can be reduced as: # # prev | curr | next # # (0) * cnt[a] * (cnt[b] + cnt[c] + cnt[d]) # (cnt[a]) * cnt[b] * (cnt[c] + cnt[d]) # (cnt[a] + cnt[b]) * cnt[c] * (cnt[d]) # (cnt[a] + cnt[b] + cnt[c]) * cnt[d] * (0) class Solution: def unequalTriplets(self, nums: List[int]) -> int: ans = 0 prev = 0 next = len(nums) for freq in collections.Counter(nums).values(): next -= freq ans += prev * freq * next prev += freq return ans