Maximum sum of almost unique subarray

Array Hash Table Sliding Window

40.8% acceptance

Feb 25, 2026

317

139

You are given an integer array nums and two positive integers m and k. Return the maximum sum out of all almost unique subarrays of length k of nums. If no such subarray exists, return 0. A subarray of nums is almost unique if it contains at least m distinct elements. A subarray is a contiguous non-empty sequence of elements within an array.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_sum(nums: Vec<i32>, m: i32, k: i32) -> i64 {
    use std::collections::HashMap;
    let m = m as usize; let k = k as usize;
    let mut freq: HashMap<i32, usize> = HashMap::new();
    let mut sum = 0i64;
    let mut ans = 0i64;
    for r in 0..nums.len() {
      sum += nums[r] as i64;
      *freq.entry(nums[r]).or_insert(0) += 1;
      if r >= k {
        let left = nums[r - k];
        sum -= left as i64;
        let e = freq.get_mut(&left).unwrap();
        *e -= 1;
        if *e == 0 { freq.remove(&left); }
      }
      if r >= k - 1 && freq.len() >= m { ans = ans.max(sum); }
    }
    ans
  }
}