Skip to content

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<int>& nums) {
    int ans = 0;
    int prev = 0;
    int next = nums.size();
    unordered_map<int, int> 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<Integer, Integer> 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