Skip to content

3416. Subsequences with a Unique Middle Mode II

  • 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
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
// Recall from solution 1 that after counting all the subsequences with `a` as
// the middle mode number, we need to subtract the cases where `a` is not a
// unique mode or not a mode.
//
// To avoid the need of looping through all numbers that are not `a`, we can
// maintain the sums that are not related to `a` in the loop.
//
// So, during the simplification of the formula, keep the running sums of
// pss, spp, pp, ss, and ps as the first item.
// (for cleaner notation, abbreviate p[b] and s[b] to just p and s)
//
//   sum(b != a) (p[a] * p * s) * (r - sa - s)
//             + (sa * s * p) * (l - p[a] - p)
//             + (p, 2) * sa * (r - sa)
//             + (s, 2) * p[a] * (l - p[a])
//
//   sum(b != a) (p * s) * (p[a] * (r - sa)) + (p * s^2) * (-p[a])
//             + (s * p) * (sa * (l - p[a])) + (s * p^2) * (-sa)
//             + (p^2 - p) * (sa * (r - sa) / 2)
//             + (s^2 - s) * (p[a] * (l - p[a]) / 2)

class Solution {
 public:
  // Same as 3395. Subsequences with a Unique Middle Mode I
  int subsequencesWithMiddleMode(vector<int>& nums) {
    int ans = 0;
    unordered_map<int, int> p;  // prefix counter
    unordered_map<int, int> s;  // suffix counter

    for (const int num : nums)
      ++s[num];

    long pss = 0;
    long spp = 0;
    long pp = 0;
    long ss = 0;
    long ps = 0;

    for (const auto& [_, freq] : s)
      ss = (ss + static_cast<long>(freq) * freq) % kMod;

    for (int i = 0; i < nums.size(); ++i) {
      const int a = nums[i];
      long sa = s[a];
      const long pa = p[a];

      // Update running sums after decrementing sa.
      pss = (pss + pa * (-sa * sa + (sa - 1) * (sa - 1))) % kMod;
      spp = (spp - pa * pa) % kMod;  // (-sa + (sa - 1)) * pa * pa
      ss = (ss - sa * sa + (sa - 1) * (sa - 1)) % kMod;
      ps = (ps - pa) % kMod;  // -pa * (-sa + (sa - 1))

      sa = --s[a];

      const int l = i;
      const int r = nums.size() - i - 1;

      // Start with all possible subsequences with `a` as the middle number.
      ans = (ans + nC2(l) * nC2(r)) % kMod;

      // Minus cases where frequency of `a` is 1, so it's not a mode.
      ans = (ans - nC2(l - pa) * nC2(r - sa)) % kMod;

      // Minus the values where `b != a`.
      const long pss_ = (pss - pa * sa * sa) % kMod;
      const long spp_ = (spp - sa * pa * pa) % kMod;
      const long pp_ = (pp - pa * pa) % kMod;
      const long ss_ = (ss - sa * sa) % kMod;
      const long ps_ = (ps - pa * sa) % kMod;
      const long p_ = l - pa;
      const long s_ = r - sa;

      // Minus cases where `a` is not a "unique" mode or not a mode.
      long subtract = 0;
      subtract = (subtract + ps_ * (pa * (r - sa))) % kMod;
      subtract = (subtract + pss_ * (-pa)) % kMod;
      subtract = (subtract + ps_ * (sa * (l - pa))) % kMod;
      subtract = (subtract + spp_ * (-sa)) % kMod;
      subtract = (subtract + (pp_ - p_) * sa * (r - sa) / 2) % kMod;
      subtract = (subtract + (ss_ - s_) * pa * (l - pa) / 2) % kMod;
      ans = (ans - subtract + kMod) % kMod;

      // Update running sums after incrementing p[a].
      pss = (pss + sa * sa) % kMod;  // (-pa + (pa + 1)) * sa * sa
      spp = (spp + sa * (-pa * pa + (pa + 1) * (pa + 1))) % kMod;
      pp = (pp - pa * pa + (pa + 1) * (pa + 1)) % kMod;
      ps = (ps + sa) % kMod;  // (-pa + (pa + 1)) * sa

      ++p[a];
    }

    return (ans + kMod) % kMod;
  }

 private:
  static constexpr int kMod = 1'000'000'007;

  // Returns C(n, 2)
  long nC2(long n) {
    return n * (n - 1) / 2 % kMod;
  }
};

  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
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
// Recall from solution 1 that after counting all the subsequences with `a` as
// the middle mode number, we need to subtract the cases where `a` is not a
// unique mode or not a mode.
//
// To avoid the need of looping through all numbers that are not `a`, we can
// maintain the sums that are not related to `a` in the loop.
//
// So, during the simplification of the formula, keep the running sums of
// pss, spp, pp, ss, and ps as the first item.
// (for cleaner notation, abbreviate p[b] and s[b] to just p and s)
//
//   sum(b != a) (p[a] * p * s) * (r - s[a] - s)
//             + (s[a] * s * p) * (l - p[a] - p)
//             + (p, 2) * s[a] * (r - s[a])
//             + (s, 2) * p[a] * (l - p[a])
//
//   sum(b != a) (p * s) * (p[a] * (r - s[a])) + (p * s^2) * (-p[a])
//             + (s * p) * (s[a] * (l - p[a])) + (s * p^2) * (-s[a])
//             + (p^2 - p) * (s[a] * (r - s[a]) / 2)
//             + (s^2 - s) * (p[a] * (l - p[a]) / 2)

class Solution {
  // Same as 3395. Subsequences with a Unique Middle Mode I
  public int subsequencesWithMiddleMode(int[] nums) {
    int ans = 0;
    Map<Integer, Integer> p = new HashMap<>(); // prefix counter
    Map<Integer, Integer> s = new HashMap<>(); // suffix counter

    for (final int num : nums)
      s.merge(num, 1, Integer::sum);

    long pss = 0;
    long spp = 0;
    long pp = 0;
    long ss = 0;
    long ps = 0;

    for (final int freq : s.values())
      ss = (ss + (long) freq * freq) % MOD;

    for (int i = 0; i < nums.length; ++i) {
      final int a = nums[i];
      long sa = s.get(a);
      final long pa = p.getOrDefault(a, 0);

      // Update running sums after decrementing s[a]
      pss = (pss + pa * (-sa * sa + (sa - 1) * (sa - 1))) % MOD;
      spp = (spp - pa * pa) % MOD; // (-sa + (sa - 1)) * pa * pa
      ss = (ss - sa * sa + (sa - 1) * (sa - 1)) % MOD;
      ps = (ps - pa) % MOD; // -pa * (-sa + (sa - 1))

      s.merge(a, -1, Integer::sum);
      sa = s.get(a);

      final int l = i;
      final int r = nums.length - i - 1;

      // Start with all possible subsequences with `a` as the middle number
      ans = (int) ((ans + (long) nC2(l) * nC2(r)) % MOD);

      // Minus cases where frequency of `a` is 1, so it's not a mode
      ans = (int) ((ans - (long) nC2(l - pa) * nC2(r - sa)) % MOD);

      // Minus the values where `b != a`
      final long pss_ = (pss - pa * sa * sa) % MOD;
      final long spp_ = (spp - sa * pa * pa) % MOD;
      final long pp_ = (pp - pa * pa) % MOD;
      final long ss_ = (ss - sa * sa) % MOD;
      final long ps_ = (ps - pa * sa) % MOD;
      final long p_ = l - pa;
      final long s_ = r - sa;

      // Minus cases where `a` is not a "unique" mode or not a mode
      long subtract = 0;
      subtract = (subtract + ps_ * (pa * (r - sa))) % MOD;
      subtract = (subtract + pss_ * (-pa)) % MOD;
      subtract = (subtract + ps_ * (sa * (l - pa))) % MOD;
      subtract = (subtract + spp_ * (-sa)) % MOD;
      subtract = (subtract + (pp_ - p_) * sa * (r - sa) / 2) % MOD;
      subtract = (subtract + (ss_ - s_) * pa * (l - pa) / 2) % MOD;
      ans = (int) ((ans - subtract + MOD) % MOD);

      // Update running sums after incrementing p[a]
      pss = (pss + sa * sa) % MOD; // (-pa + (pa + 1)) * sa * sa
      spp = (spp + sa * (-pa * pa + (pa + 1) * (pa + 1))) % MOD;
      pp = (pp - pa * pa + (pa + 1) * (pa + 1)) % MOD;
      ps = (ps + sa) % MOD; // (-pa + (pa + 1)) * sa

      p.merge(a, 1, Integer::sum);
    }

    return (int) ((ans + MOD) % MOD);
  }

  private static final int MOD = 1_000_000_007;

  // Returns C(n, 2)
  private long nC2(long n) {
    return n * (n - 1) / 2 % MOD;
  }
}

 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
# Recall from solution 1 that after counting all the subsequences with `a` as
# the middle mode number, we need to subtract the cases where `a` is not a
# unique mode or not a mode.
#
# To avoid the need of looping through all numbers that are not `a`, we can
# maintain the sums that are not related to `a` in the loop.
#
# So, during the simplification of the formula, keep the running sums of
# pss, spp, pp, ss, and ps as the first item.
# (for cleaner notation, abbreviate p[b] and s[b] to just p and s)
#
#   sum(b != a) (p[a] * p * s) * (r - s[a] - s)
#             + (s[a] * s * p) * (l - p[a] - p)
#             + (p, 2) * s[a] * (r - s[a])
#             + (s, 2) * p[a] * (l - p[a])
#
#   sum(b != a) (p * s) * (p[a] * (r - s[a])) + (p * s^2) * (-p[a])
#             + (s * p) * (s[a] * (l - p[a])) + (s * p^2) * (-s[a])
#             + (p^2 - p) * (s[a] * (r - s[a]) / 2)
#             + (s^2 - s) * (p[a] * (l - p[a]) / 2)


class Solution:
  # Same as 3395. Subsequences with a Unique Middle Mode I
  def subsequencesWithMiddleMode(self, nums: list[int]) -> int:
    MOD = 1_000_000_007
    ans = 0
    p = collections.Counter()  # prefix counter
    s = collections.Counter(nums)  # suffix counter

    def nC2(n: int) -> int:
      return n * (n - 1) // 2

    pss = 0
    spp = 0
    pp = 0
    ss = sum(freq**2 for freq in s.values())
    ps = 0

    for i, a in enumerate(nums):
      # Update running sums after decrementing s[a].
      pss += p[a] * (-s[a]**2 + (s[a] - 1)**2)
      spp += -p[a]**2  # (-s[a] + (s[a] - 1)) * p[a]**2
      ss += -s[a]**2 + (s[a] - 1)**2
      ps += -p[a]  # -p[a] * (-s[a] + (s[a] - 1))

      s[a] -= 1

      l = i
      r = len(nums) - i - 1

      # Start with all possible subsequences with `a` as the middle number.
      ans += nC2(l) * nC2(r)

      # Minus the cases where the frequency of `a` is 1, so it's not a mode.
      ans -= nC2(l - p[a]) * nC2(r - s[a])

      # Minus the values where `b != a`.
      pss_ = pss - p[a] * s[a]**2
      spp_ = spp - s[a] * p[a]**2
      pp_ = pp - p[a]**2
      ss_ = ss - s[a]**2
      ps_ = ps - p[a] * s[a]
      p_ = l - p[a]
      s_ = r - s[a]

      # Minus the cases where the `a` is not a "unique" mode or not a mode.
      ans -= ps_ * (p[a] * (r - s[a])) + pss_ * (-p[a])
      ans -= ps_ * (s[a] * (l - p[a])) + spp_ * (-s[a])
      ans -= (pp_ - p_) * s[a] * (r - s[a]) // 2
      ans -= (ss_ - s_) * p[a] * (l - p[a]) // 2
      ans %= MOD

      # Update running sums after incrementing p[a].
      pss += s[a]**2  # (-p[a] + (p[a] + 1)) * s[a]**2
      spp += s[a] * (-p[a]**2 + (p[a] + 1)**2)
      pp += -p[a]**2 + (p[a] + 1)**2
      ps += s[a]  # (-p[a] + (p[a] + 1)) * s[a]

      p[a] += 1

    return ans