Count the number of good partitions

Array Hash Table Math Combinatorics

49.0% acceptance

Feb 25, 2026

307

You are given a 0-indexed array nums consisting of positive integers. A partition of an array into one or more contiguous subarrays is called good if no two subarrays contain the same number. Return the total number of good partitions of nums. Since the answer may be large, return it modulo 109 + 7.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn number_of_good_partitions(nums: Vec<i32>) -> i32 {
    use std::collections::HashMap;
    const MOD: u64 = 1_000_000_007;

    let n = nums.len();
    // For each value, record its last occurrence
    let mut last: HashMap<i32, usize> = HashMap::new();
    for (i, &v) in nums.iter().enumerate() {
      last.insert(v, i);
    }

    let mut ans = 1u64;
    let mut cur_end = 0usize;
    let mut segments = 0u32;

    for i in 0..n {
      cur_end = cur_end.max(*last.get(&nums[i]).unwrap());
      if i == cur_end {
        segments += 1;
      }
    }

    // 2^(segments - 1) mod MOD
    if segments > 1 {
      ans = 1;
      let mut base = 2u64;
      let mut exp = (segments - 1) as u64;
      while exp > 0 {
        if exp & 1 == 1 { ans = ans * base % MOD; }
        base = base * base % MOD;
        exp >>= 1;
      }
    }

    ans as i32
  }
}