Sliding subarray beauty

Array Hash Table Sliding Window

36.4% acceptance

Feb 25, 2026

741

140

Given an integer array nums containing n integers, find the beauty of each subarray of size k. The beauty of a subarray is the xth smallest integer in the subarray if it is negative, or 0 if there are fewer than x negative integers. Return an integer array containing n - k + 1 integers, which denote the beauty of the subarrays in order from the first index in the array.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn get_subarray_beauty(nums: Vec<i32>, k: i32, x: i32) -> Vec<i32> {
    let n = nums.len();
    let k = k as usize;
    let x = x as usize;
    // Frequency array for values -50 to 50 (offset by 50)
    let mut freq = [0i32; 101];

    let mut result = Vec::with_capacity(n - k + 1);

    for i in 0..n {
      // Add nums[i] to window
      freq[(nums[i] + 50) as usize] += 1;

      // Remove nums[i-k] from window when window is full
      if i >= k {
        freq[(nums[i - k] + 50) as usize] -= 1;
      }

      // Compute xth smallest negative
      if i + 1 >= k {
        let mut count = 0;
        let mut beauty = 0i32;
        for v in -50i32..0 {
          count += freq[(v + 50) as usize] as usize;
          if count >= x {
            beauty = v;
            break;
          }
        }
        result.push(beauty);
      }
    }
    result
  }
}