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.

See Leetcode 3416 for full details and examples.

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#

Solution#

Method 1 - Enumerate Middle, Count Ways#

Intuition#

Approach#

Code#

Complexity#