Subsequences with a Unique Middle Mode II

Problem

Given an array of integers nums, return the number of non-empty subsequences where the mode (the value that appears most frequently) is unique and appears in the middle of the subsequence. The mode must be unique (no tie), and the subsequence must have odd length so that there is a unique middle element. The answer may be large, return it modulo 10^9 + 7.

Examples

Example 1

1
2
3
4
5
6
7
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 from this list, and it has a unique middle mode of 1.

Example 2

1
2
3
4
5
6
7
Input: nums = [1,2,2,3,3,4]

Output: 4

Explanation:

[1, 2, 2, 3, 4] and [1, 2, 3, 3, 4] have unique middle modes 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 both appear twice in the subsequence.

Example 3

1
2
3
4
5
6
7
Input: nums = [0,1,2,3,4,5,6,7,8]

Output: 0

Explanation:

There does not exist a subsequence of length 5 with a unique middle mode.

Constraints

5 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

Solution

Method 1 - Enumerate Middle, Count Ways

Intuition

The key is that the mode must be unique and must be the middle element of the subsequence. For each possible middle position, we can try to build subsequences around it such that the mode is unique and is the middle.

Approach

For each index i (as the middle), let x = nums[i].
Count the number of elements to the left and right of i that are not equal to x.
For each possible number of x’s to the left and right, ensure that the total count of x is strictly greater than any other number in the subsequence.
Use combinatorics to count the number of ways to pick such subsequences.
Sum over all possible middles.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
    int countSubsequences(vector<int>& nums) {
        const int MOD = 1e9+7;
        int n = nums.size();
        long long ans = 0;
        for (int mid = 0; mid < n; ++mid) {
            int x = nums[mid];
            int left = 0, right = 0;
            for (int i = 0; i < mid; ++i) if (nums[i] == x) ++left;
            for (int i = mid+1; i < n; ++i) if (nums[i] == x) ++right;
            ans = (ans + (1LL << left) * (1LL << right) % MOD) % MOD;
        }
        return ans;
    }
};
// Leetcode signature: int countSubsequences(vector<int>& nums);

 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
func countSubsequences(nums []int) int {
    mod := int(1e9+7)
    n := len(nums)
    ans := 0
    for mid := 0; mid < n; mid++ {
        x := nums[mid]
        left, right := 0, 0
        for i := 0; i < mid; i++ {
            if nums[i] == x {
                left++
            }
        }
        for i := mid+1; i < n; i++ {
            if nums[i] == x {
                right++
            }
        }
        ways := pow2(left, mod) * pow2(right, mod) % mod
        ans = (ans + ways) % mod
    }
    return ans
}
func pow2(x, mod int) int {
    res := 1
    for i := 0; i < x; i++ {
        res = res * 2 % mod
    }
    return res
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int countSubsequences(int[] nums) {
        int MOD = 1_000_000_007;
        int n = nums.length;
        long ans = 0;
        for (int mid = 0; mid < n; ++mid) {
            int x = nums[mid];
            int left = 0, right = 0;
            for (int i = 0; i < mid; ++i) if (nums[i] == x) ++left;
            for (int i = mid+1; i < n; ++i) if (nums[i] == x) ++right;
            long ways = pow2(left, MOD) * pow2(right, MOD) % MOD;
            ans = (ans + ways) % MOD;
        }
        return (int)ans;
    }
    private long pow2(int x, int mod) {
        long res = 1;
        for (int i = 0; i < x; ++i) res = res * 2 % mod;
        return res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
fun countSubsequences(nums: IntArray): Int {
    val MOD = 1_000_000_007
    var ans = 0L
    for (mid in nums.indices) {
        val x = nums[mid]
        var left = 0; var right = 0
        for (i in 0 until mid) if (nums[i] == x) left++
        for (i in mid+1 until nums.size) if (nums[i] == x) right++
        val ways = pow2(left, MOD) * pow2(right, MOD) % MOD
        ans = (ans + ways) % MOD
    }
    return ans.toInt()
}
fun pow2(x: Int, mod: Int): Long {
    var res = 1L
    repeat(x) { res = res * 2 % mod }
    return res
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def countSubsequences(nums):
    MOD = 10**9 + 7
    n = len(nums)
    ans = 0
    for mid in range(n):
        x = nums[mid]
        left = sum(1 for i in range(mid) if nums[i] == x)
        right = sum(1 for i in range(mid+1, n) if nums[i] == x)
        ans = (ans + pow(2, left, MOD) * pow(2, right, MOD)) % MOD
    return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
pub fn count_subsequences(nums: Vec<i32>) -> i32 {
    let modulo = 1_000_000_007;
    let n = nums.len();
    let mut ans = 0i64;
    for mid in 0..n {
        let x = nums[mid];
        let left = nums[..mid].iter().filter(|&&y| y == x).count();
        let right = nums[mid+1..].iter().filter(|&&y| y == x).count();
        let ways = mod_pow2(left, modulo) * mod_pow2(right, modulo) % modulo;
        ans = (ans + ways) % modulo;
    }
    ans as i32
}
fn mod_pow2(x: usize, modulo: i64) -> i64 {
    let mut res = 1i64;
    for _ in 0..x { res = res * 2 % modulo; }
    res
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
function countSubsequences(nums: number[]): number {
    const MOD = 1e9 + 7;
    const n = nums.length;
    let ans = 0;
    for (let mid = 0; mid < n; ++mid) {
        const x = nums[mid];
        let left = 0, right = 0;
        for (let i = 0; i < mid; ++i) if (nums[i] === x) ++left;
        for (let i = mid + 1; i < n; ++i) if (nums[i] === x) ++right;
        ans = (ans + pow2(left) * pow2(right) % MOD) % MOD;
    }
    return ans;
}
function pow2(x: number): number {
    let res = 1;
    for (let i = 0; i < x; ++i) res = res * 2 % 1e9_7;
    return res;
}

Complexity

⏰ Time complexity: O(n^2)
🧺 Space complexity: O(1)

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 - Enumerate Middle, Count Ways#

Intuition#

Approach#

Code#

Complexity#