3395. Subsequences with a Unique Middle Mode I LeetCode Solution
In this guide, you will get 3395. Subsequences with a Unique Middle Mode I LeetCode Solution with the best time and space complexity. The solution to Subsequences with a Unique Middle Mode I problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Subsequences with a Unique Middle Mode I
Given an integer array nums, find the number of subsequences of size 5 of nums with a unique middle mode.
Since the answer may be very large, return it modulo 109 + 7.
A mode of a sequence of numbers is defined as the element that appears the maximum number of times in the sequence.
A sequence of numbers contains a unique mode if it has only one mode.
A sequence of numbers seq of size 5 contains a unique middle mode if the middle element (seq[2]) is a unique mode.
Example 1:
Input: nums = [1,1,1,1,1,1]
Output: 6
Explanation:
[1, 1, 1, 1, 1] is the only subsequence of size 5 that can be formed, and it has a unique middle mode of 1. This subsequence can be formed in 6 different ways, so the output is 6.
Example 2:
Input: nums = [1,2,2,3,3,4]
Output: 4
Explanation:
[1, 2, 2, 3, 4] and [1, 2, 3, 3, 4] each have a unique middle mode because the number at index 2 has the greatest frequency in the subsequence. [1, 2, 2, 3, 3] does not have a unique middle mode because 2 and 3 appear twice.
Example 3:
Input: nums = [0,1,2,3,4,5,6,7,8]
Output: 0
Explanation:
There is no subsequence of length 5 with a unique middle mode.
Constraints:
5 <= nums.length <= 1000
-109 <= nums[i] <= 109
Complexity Analysis
Time Complexity: O(n^2)
Space Complexity: O(n)
3395. Subsequences with a Unique Middle Mode I LeetCode Solution in C++
class Solution {
public:
int subsequencesWithMiddleMode(vector<int>& nums) {
const int n = nums.size();
long ans = 0;
unordered_map<int, int> left;
unordered_map<int, int> right;
for (int i = 0; i < 2; ++i)
++left[nums[i]];
for (int i = 2; i < n; ++i)
++right[nums[i]];
for (int i = 2; i < n - 2; ++i) {
const int num = nums[i];
if (--right[num] == 0)
right.erase(num);
const int leftCount = left[num];
const int rightCount = right[num];
const int leftOther = i - leftCount;
const int rightOther = n - 1 - i - rightCount;
// count[mode] = 5 -- [a a] a [a a]
ans += nC2(leftCount) * nC2(rightCount);
ans %= kMod;
// count[mode] = 4 -- [a a] a [a ?]
ans += nC2(leftCount) * rightCount % kMod * rightOther % kMod;
ans %= kMod;
// count[mode] = 4 -- [a ?] a [a a]
ans += leftCount * leftOther % kMod * nC2(rightCount) % kMod;
ans %= kMod;
// count[mode] = 3 -- [a a] a [? ?]
ans += nC2(leftCount) * nC2(rightOther) % kMod;
ans %= kMod;
// count[mode] = 3 -- [? ?] a [a a]
ans += nC2(leftOther) * nC2(rightCount) % kMod;
ans %= kMod;
// count[mode] = 3 -- [a ?] a [a ?]
ans +=
leftCount * leftOther % kMod * rightCount % kMod * rightOther % kMod;
ans %= kMod;
// count[mode] = 2 -- [a ?] a [? ?]
ans += leftCount * calc(num, leftOther, rightOther, left, right) % kMod;
ans %= kMod;
// count[mode] = 2 -- [? ?] a [a ?]
ans += rightCount * calc(num, rightOther, leftOther, right, left) % kMod;
ans %= kMod;
++left[num];
}
return ans % kMod;
}
private:
static constexpr int kMod = 1'000'000'007;
// Returns C(n, 2).
long nC2(long n) {
return n * (n - 1) / 2 % kMod;
}
// Returns the count of subsequences that have `a` as the middle number, where
// invalid subsequences are excluded.
long calc(int a, long other1, long other2,
const unordered_map<int, int>& count1,
const unordered_map<int, int>& count2) {
// [a ?] a [? ?]
long res = other1 * nC2(other2) % kMod;
for (const auto& [b, b1] : count1) {
if (b == a)
continue;
const long b2 = count2.contains(b) ? count2.at(b) : 0;
// Exclude triples -- [a b] a [b b].
res = (res - b1 * nC2(b2) % kMod + kMod) % kMod;
// Exclude doubles -- [a b] a [b ?].
res = (res - b1 * b2 % kMod * (other2 - b2) % kMod + kMod) % kMod;
}
for (const auto& [b, b2] : count2) {
if (b == a)
continue;
const long b1 = count1.contains(b) ? count1.at(b) : 0;
// Exclude doubles -- [a ?] a [b b].
res = (res - (other1 - b1) * nC2(b2) % kMod + kMod) % kMod;
}
return res;
}
}; /* code provided by PROGIEZ */
3395. Subsequences with a Unique Middle Mode I LeetCode Solution in Java
class Solution {
public int subsequencesWithMiddleMode(int[] nums) {
int n = nums.length;
long ans = 0;
Map<Integer, Integer> left = new HashMap<>();
Map<Integer, Integer> right = new HashMap<>();
for (int i = 0; i < 2; ++i)
left.merge(nums[i], 1, Integer::sum);
for (int i = 2; i < n; ++i)
right.merge(nums[i], 1, Integer::sum);
for (int i = 2; i < n - 2; ++i) {
final int num = nums[i];
if (right.merge(num, -1, Integer::sum) == 0)
right.remove(num);
final int leftCount = left.getOrDefault(num, 0);
final int rightCount = right.getOrDefault(num, 0);
final int leftOther = i - leftCount;
final int rightOther = n - 1 - i - rightCount;
// count[mode] = 5 -- [a a] a [a a]
ans = (ans + nC2(leftCount) * nC2(rightCount)) % kMod;
// count[mode] = 4 -- [a a] a [a ?]
ans = (ans + nC2(leftCount) * rightCount % kMod * rightOther % kMod) % kMod;
// count[mode] = 4 -- [a ?] a [a a]
ans = (ans + leftCount * leftOther % kMod * nC2(rightCount) % kMod) % kMod;
// count[mode] = 3 -- [a a] a [? ?]
ans = (ans + nC2(leftCount) * nC2(rightOther) % kMod) % kMod;
// count[mode] = 3 -- [? ?] a [a a]
ans = (ans + nC2(leftOther) * nC2(rightCount) % kMod) % kMod;
// count[mode] = 3 -- [a ?] a [a ?]
ans = (ans + leftCount * leftOther % kMod * rightCount % kMod * rightOther % kMod) % kMod;
// count[mode] = 2 -- [a ?] a [? ?]
ans = (ans + leftCount * calc(num, leftOther, rightOther, left, right) % kMod) % kMod;
// count[mode] = 2 -- [? ?] a [a ?]
ans = (ans + rightCount * calc(num, rightOther, leftOther, right, left) % kMod) % kMod;
// Update left map
left.merge(num, 1, Integer::sum);
}
return (int) (ans % kMod);
}
private static final int kMod = 1_000_000_007;
// Returns C(n, 2)
private long nC2(long n) {
return n * (n - 1) / 2 % kMod;
}
// Returns the count of subsequences that have 'a' as the middle number, where
// invalid subsequences are excluded
private long calc(int a, long other1, long other2, Map<Integer, Integer> count1,
Map<Integer, Integer> count2) {
// [a ?] a [? ?]
long res = other1 * nC2(other2) % kMod;
for (Map.Entry<Integer, Integer> entry : count1.entrySet()) {
final int b = entry.getKey();
final long b1 = entry.getValue();
if (b == a)
continue;
final long b2 = count2.getOrDefault(b, 0);
// Exclude triples -- [a b] a [b b]
res = (res - b1 * nC2(b2) % kMod + kMod) % kMod;
// Exclude doubles -- [a b] a [b ?]
res = (res - b1 * b2 % kMod * (other2 - b2) % kMod + kMod) % kMod;
}
for (Map.Entry<Integer, Integer> entry : count2.entrySet()) {
final int b = entry.getKey();
final long b2 = entry.getValue();
if (b == a)
continue;
final long b1 = count1.getOrDefault(b, 0);
// Exclude doubles -- [a ?] a [b b]
res = (res - (other1 - b1) * nC2(b2) % kMod + kMod) % kMod;
}
return res;
}
} // code provided by PROGIEZ
3395. Subsequences with a Unique Middle Mode I LeetCode Solution in Python
class Solution:
def __init__(self):
self.kMod = 1_000_000_007
def subsequencesWithMiddleMode(self, nums: list[int]) -> int:
n = len(nums)
ans = 0
left = collections.Counter()
right = collections.Counter()
for i in range(2):
left[nums[i]] += 1
for i in range(2, n):
right[nums[i]] += 1
for i in range(2, n - 2):
num = nums[i]
right[num] -= 1
if right[num] == 0:
del right[num]
leftCount = left[num]
rightCount = right[num]
leftOther = i - leftCount
rightOther = n - 1 - i - rightCount
# count[mode] = 5 -- [a a] a [a a]
ans += math.comb(leftCount, 2) * math.comb(rightCount, 2)
# count[mode] = 4 -- [a a] a [a ?]
ans += math.comb(leftCount, 2) * rightCount * rightOther
# count[mode] = 4 -- [a ?] a [a a]
ans += leftCount * leftOther * math.comb(rightCount, 2)
# count[mode] = 3 -- [a a] a [? ?]
ans += math.comb(leftCount, 2) * math.comb(rightOther, 2)
# count[mode] = 3 -- [? ?] a [a a]
ans += math.comb(leftOther, 2) * math.comb(rightCount, 2)
# count[mode] = 3 -- [a ?] a [a ?]
ans += leftCount * leftOther * rightCount * rightOther
# count[mode] = 2 -- [a ?] a [? ?]
ans += leftCount * self._calc(num, leftOther, rightOther, left, right)
# count[mode] = 2 -- [? ?] a [a ?]
ans += rightCount * self._calc(num, rightOther, leftOther, right, left)
ans %= self.kMod
left[num] += 1
return ans
def _calc(
self,
a: int,
other1: int,
other2: int,
count1: dict[int, int],
count2: dict[int, int]
) -> int:
"""
Returns the count of subsequences that have `a` as the middle number, where
invalid subsequences are excluded.
"""
# [a ?] a [? ?]
res = (other1 * math.comb(other2, 2)) % self.kMod
for b, b1 in count1.items():
if b == a:
continue
b2 = count2[b]
# Exclude triples -- [a b] a [b b].
res = (res - b1 * math.comb(b2, 2)) % self.kMod
# Exclude doubles -- [a b] a [b ?].
res = (res - b1 * b2 * (other2 - b2)) % self.kMod
for b, b2 in count2.items():
if b == a:
continue
b1 = count1[b]
# Exclude doubles -- [a ?] a [b b].
res = (res - (other1 - b1) * math.comb(b2, 2)) % self.kMod
return (res + self.kMod) % self.kMod # code by PROGIEZ
