Minimum subarray length with distinct sum at least k

Array Hash Table Sliding Window

31.7% acceptance

Mar 15, 2026

You are given an integer array nums and an integer k. Return the minimum length of a subarray whose sum of the distinct values present in that subarray (each value counted once) is at least k. If no such subarray exists, return -1.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_length(nums: Vec<i32>, k: i32) -> i32 {
    use std::collections::HashMap;
    let k = k as i64;
    let n = nums.len();
    let mut count: HashMap<i32, i32> = HashMap::new();
    let mut distinct_sum: i64 = 0;
    let mut ans = i32::MAX;
    let mut left = 0;
    for right in 0..n {
      let v = nums[right];
      let e = count.entry(v).or_insert(0);
      if *e == 0 {
        distinct_sum += v as i64;
      }
      *e += 1;
      while distinct_sum >= k {
        ans = ans.min((right - left + 1) as i32);
        let lv = nums[left];
        let e = count.get_mut(&lv).unwrap();
        *e -= 1;
        if *e == 0 {
          distinct_sum -= lv as i64;
        }
        left += 1;
      }
    }
    if ans == i32::MAX { -1 } else { ans }
  }
}