Subsequences with a unique middle mode ii

Array Hash Table Math Combinatorics

14.1% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

impl Solution {
  pub fn subsequences_with_middle_mode(nums: Vec<i32>) -> i32 {
    const MOD: i64 = 1_000_000_007;

    fn c2(x: i64) -> i64 { x * (x - 1) / 2 }

    let n = nums.len();
    let mut val_map: HashMap<i32, usize> = HashMap::new();
    let mut id = 0usize;
    let mut mapped = vec![0usize; n];
    for i in 0..n {
      let e = val_map.entry(nums[i]).or_insert_with(|| { let v = id; id += 1; v });
      mapped[i] = *e;
    }
    let m = id;

    let mut left_count = vec![0i64; m];
    let mut right_count = vec![0i64; m];
    for i in 0..n {
      right_count[mapped[i]] += 1;
    }

    let mut sum_lc_rc: i64 = 0;
    let mut sum_lc_rc2: i64 = 0;
    let mut sum_rc_lc2: i64 = 0;
    let mut sum_crc2: i64 = 0;
    let mut sum_clc2: i64 = 0;

    for x in 0..m {
      sum_crc2 += c2(right_count[x]);
    }

    let mut ans: i64 = 0;

    for i in 0..n {
      let v = mapped[i];
      let rc_old = right_count[v];
      sum_crc2 -= c2(rc_old);
      sum_lc_rc -= left_count[v] * rc_old;
      sum_lc_rc2 -= left_count[v] * rc_old * rc_old;
      sum_rc_lc2 -= rc_old * left_count[v] * left_count[v];

      right_count[v] -= 1;
      let rc_new = right_count[v];
      sum_crc2 += c2(rc_new);
      sum_lc_rc += left_count[v] * rc_new;
      sum_lc_rc2 += left_count[v] * rc_new * rc_new;
      sum_rc_lc2 += rc_new * left_count[v] * left_count[v];

      let l = i as i64;
      let r = (n - 1 - i) as i64;
      let lv = left_count[v];
      let rv = right_count[v];
      let lo = l - lv;
      let ro = r - rv;

      if l >= 2 && r >= 2 {
        let total = c2(l) % MOD * (c2(r) % MOD) % MOD;
        let bad00 = c2(lo) % MOD * (c2(ro) % MOD) % MOD;

        let p_r = ((sum_crc2 - c2(rv)) % MOD + MOD) % MOD;
        let t1 = ((sum_lc_rc - lv * rv) % MOD + MOD) % MOD;
        let t2 = ((sum_lc_rc2 - lv * rv * rv) % MOD + MOD) % MOD;

        let bad10 = lv % MOD * ((lo % MOD * p_r % MOD + ro % MOD * t1 % MOD - t2 + MOD) % MOD) % MOD;

        let p_l = ((sum_clc2 - c2(lv)) % MOD + MOD) % MOD;
        let t3 = ((sum_rc_lc2 - rv * lv * lv) % MOD + MOD) % MOD;

        let bad01 = rv % MOD * ((ro % MOD * p_l % MOD + lo % MOD * t1 % MOD - t3 + MOD) % MOD) % MOD;

        let good = ((total - bad00 % MOD - bad10 % MOD - bad01 % MOD) % MOD + MOD) % MOD;
        ans = (ans + good) % MOD;
      }

      let lc_old = left_count[v];
      sum_clc2 -= c2(lc_old);
      sum_lc_rc -= lc_old * right_count[v];
      sum_lc_rc2 -= lc_old * right_count[v] * right_count[v];
      sum_rc_lc2 -= right_count[v] * lc_old * lc_old;

      left_count[v] += 1;
      let lc_new = left_count[v];
      sum_clc2 += c2(lc_new);
      sum_lc_rc += lc_new * right_count[v];
      sum_lc_rc2 += lc_new * right_count[v] * right_count[v];
      sum_rc_lc2 += right_count[v] * lc_new * lc_new;
    }

    ans as i32
  }
}