Subsequences with a Unique Middle Mode I

Problem

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 10^9 + 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 aunique 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.

Examples

Example 1

Input:s = [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:s = [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:s = [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
• -10^9 <= nums[i] <= 10^9

Solution

Method 1 - Enumerate All Subsequences of Length 5

Intuition

We need to count all subsequences of length 5 where the middle element is the unique mode. Since n ≤ 1000, we can enumerate all possible 5-element subsequences (using 5 nested loops or combinations), check the mode, and count if the middle is the unique mode.

Approach

1. For every increasing tuple of indices (i, j, k, l, m) with i < j < k < l < m, form the subsequence [nums[i], nums[j], nums[k], nums[l], nums[m]].
2. Count the frequency of each element in the subsequence.
3. The mode is unique if only one value has the maximum frequency.
4. If the middle element (nums[k]) is the unique mode, increment the answer.
5. Return the answer modulo 10^9+7.

Code

C++

#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 i = 0; i < n; ++i)
        for (int j = i+1; j < n; ++j)
        for (int k = j+1; k < n; ++k)
        for (int l = k+1; l < n; ++l)
        for (int m = l+1; m < n; ++m) {
            vector<int> seq = {nums[i], nums[j], nums[k], nums[l], nums[m]};
            unordered_map<int, int> freq;
            for (int x : seq) freq[x]++;
            int maxf = 0, cnt = 0, mode = 0;
            for (auto& [val, f] : freq) {
                if (f > maxf) { maxf = f; cnt = 1; mode = val; }
                else if (f == maxf) cnt++;
            }
            if (cnt == 1 && seq[2] == mode) ans = (ans + 1) % MOD;
        }
        return ans;
    }
};
// Leetcode signature: int countSubsequences(vector<int>& nums);

Go

func countSubsequences(nums []int) int {
    mod := int(1e9+7)
    n := len(nums)
    ans := 0
    for i := 0; i < n; i++ {
        for j := i+1; j < n; j++ {
            for k := j+1; k < n; k++ {
                for l := k+1; l < n; l++ {
                    for m := l+1; m < n; m++ {
                        seq := []int{nums[i], nums[j], nums[k], nums[l], nums[m]}
                        freq := map[int]int{}
                        for _, x := range seq { freq[x]++ }
                        maxf, cnt, mode := 0, 0, 0
                        for v, f := range freq {
                            if f > maxf { maxf, cnt, mode = f, 1, v }
                            else if f == maxf { cnt++ }
                        }
                        if cnt == 1 && seq[2] == mode {
                            ans = (ans + 1) % mod
                        }
                    }
                }
            }
        }
    }
    return ans
}

Java

import java.util.*;
class Solution {
    public int countSubsequences(int[] nums) {
        int MOD = 1_000_000_007, n = nums.length;
        long ans = 0;
        for (int i = 0; i < n; ++i)
        for (int j = i+1; j < n; ++j)
        for (int k = j+1; k < n; ++k)
        for (int l = k+1; l < n; ++l)
        for (int m = l+1; m < n; ++m) {
            int[] seq = {nums[i], nums[j], nums[k], nums[l], nums[m]};
            Map<Integer, Integer> freq = new HashMap<>();
            for (int x : seq) freq.put(x, freq.getOrDefault(x, 0) + 1);
            int maxf = 0, cnt = 0, mode = 0;
            for (int v : freq.keySet()) {
                int f = freq.get(v);
                if (f > maxf) { maxf = f; cnt = 1; mode = v; }
                else if (f == maxf) cnt++;
            }
            if (cnt == 1 && seq[2] == mode) ans = (ans + 1) % MOD;
        }
        return (int)ans;
    }
}

Kotlin

fun countSubsequences(nums: IntArray): Int {
    val MOD = 1_000_000_007
    val n = nums.size
    var ans = 0L
    for (i in 0 until n)
    for (j in i+1 until n)
    for (k in j+1 until n)
    for (l in k+1 until n)
    for (m in l+1 until n) {
        val seq = listOf(nums[i], nums[j], nums[k], nums[l], nums[m])
        val freq = seq.groupingBy { it }.eachCount()
        val maxf = freq.values.maxOrNull() ?: 0
        val modes = freq.filterValues { it == maxf }.keys
        if (modes.size == 1 && seq[2] == modes.first()) ans = (ans + 1) % MOD
    }
    return ans.toInt()
}

Python

def countSubsequences(nums):
    from collections import Counter
    MOD = 10**9 + 7
    n = len(nums)
    ans = 0
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                for l in range(k+1, n):
                    for m in range(l+1, n):
                        seq = [nums[i], nums[j], nums[k], nums[l], nums[m]]
                        freq = Counter(seq)
                        maxf = max(freq.values())
                        modes = [x for x in freq if freq[x] == maxf]
                        if len(modes) == 1 and seq[2] == modes[0]:
                            ans = (ans + 1) % MOD
    return ans

Rust

use std::collections::HashMap;
pub fn count_subsequences(nums: Vec<i32>) -> i32 {
    let modulo = 1_000_000_007;
    let n = nums.len();
    let mut ans = 0i64;
    for i in 0..n {
        for j in i+1..n {
            for k in j+1..n {
                for l in k+1..n {
                    for m in l+1..n {
                        let seq = [nums[i], nums[j], nums[k], nums[l], nums[m]];
                        let mut freq = HashMap::new();
                        for &x in &seq { *freq.entry(x).or_insert(0) += 1; }
                        let maxf = *freq.values().max().unwrap();
                        let modes: Vec<_> = freq.iter().filter(|(_, &v)| v == maxf).map(|(&k, _)| k).collect();
                        if modes.len() == 1 && seq[2] == modes[0] { ans = (ans + 1) % modulo; }
                    }
                }
            }
        }
    }
    ans as i32
}

TypeScript

function countSubsequences(nums: number[]): number {
    const MOD = 1e9 + 7;
    const n = nums.length;
    let ans = 0;
    for (let i = 0; i < n; ++i)
    for (let j = i+1; j < n; ++j)
    for (let k = j+1; k < n; ++k)
    for (let l = k+1; l < n; ++l)
    for (let m = l+1; m < n; ++m) {
        const seq = [nums[i], nums[j], nums[k], nums[l], nums[m]];
        const freq: Record<number, number> = {};
        for (const x of seq) freq[x] = (freq[x] || 0) + 1;
        const maxf = Math.max(...Object.values(freq));
        const modes = Object.keys(freq).filter(x => freq[+x] === maxf).map(Number);
        if (modes.length === 1 && seq[2] === modes[0]) ans = (ans + 1) % MOD;
    }
    return ans;
}

Complexity

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