2653. Sliding Subarray Beauty LeetCode Solution

Last updated: March 5, 2025

In this guide, you will get 2653. Sliding Subarray Beauty LeetCode Solution with the best time and space complexity. The solution to Sliding Subarray Beauty problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Sliding Subarray Beauty solution in C++
Sliding Subarray Beauty solution in Java
Sliding Subarray Beauty solution in Python
Additional Resources

2653. Sliding Subarray Beauty LeetCode Solution image

Problem Statement of Sliding Subarray Beauty

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.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,-1,-3,-2,3], k = 3, x = 2
Output: [-1,-2,-2]
Explanation: There are 3 subarrays with size k = 3.
The first subarray is [1, -1, -3] and the 2nd smallest negative integer is -1.
The second subarray is [-1, -3, -2] and the 2nd smallest negative integer is -2.
The third subarray is [-3, -2, 3] and the 2nd smallest negative integer is -2.
Example 2:

Input: nums = [-1,-2,-3,-4,-5], k = 2, x = 2
Output: [-1,-2,-3,-4]
Explanation: There are 4 subarrays with size k = 2.
For [-1, -2], the 2nd smallest negative integer is -1.
For [-2, -3], the 2nd smallest negative integer is -2.
For [-3, -4], the 2nd smallest negative integer is -3.
For [-4, -5], the 2nd smallest negative integer is -4.
Example 3:

Input: nums = [-3,1,2,-3,0,-3], k = 2, x = 1
Output: [-3,0,-3,-3,-3]
Explanation: There are 5 subarrays with size k = 2.
For [-3, 1], the 1st smallest negative integer is -3.
For [1, 2], there is no negative integer so the beauty is 0.
For [2, -3], the 1st smallest negative integer is -3.
For [-3, 0], the 1st smallest negative integer is -3.
For [0, -3], the 1st smallest negative integer is -3.

Constraints:

n == nums.length
1 <= n <= 105
1 <= k <= n
1 <= x <= k
-50 <= nums[i] <= 50

Complexity Analysis

Time Complexity: O(50n) = O(n)
Space Complexity: O(n)

2653. Sliding Subarray Beauty LeetCode Solution in C++

class Solution {
 public:
  vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {
    vector<int> ans;
    vector<int> count(50);  // count[i] := the frequency of (i + 50)

    for (int i = 0; i < nums.size(); ++i) {
      if (nums[i] < 0)
        ++count[nums[i] + 50];
      if (i - k >= 0 && nums[i - k] < 0)
        --count[nums[i - k] + 50];
      if (i + 1 >= k)
        ans.push_back(getXthSmallestNum(count, x));
    }

    return ans;
  }

 private:
  int getXthSmallestNum(const vector<int>& count, int x) {
    int prefix = 0;
    for (int i = 0; i < 50; ++i) {
      prefix += count[i];
      if (prefix >= x)
        return i - 50;
    }
    return 0;
  }
};
/* code provided by PROGIEZ */

2653. Sliding Subarray Beauty LeetCode Solution in Java

class Solution {
  public int[] getSubarrayBeauty(int[] nums, int k, int x) {
    int[] ans = new int[nums.length - k + 1];
    int[] count = new int[50]; // count[i] := the frequency of (i + 50)

    for (int i = 0; i < nums.length; ++i) {
      if (nums[i] < 0)
        ++count[nums[i] + 50];
      if (i - k >= 0 && nums[i - k] < 0)
        --count[nums[i - k] + 50];
      if (i + 1 >= k)
        ans[i - k + 1] = getXthSmallestNum(count, x);
    }

    return ans;
  }

  private int getXthSmallestNum(int[] count, int x) {
    int prefix = 0;
    for (int i = 0; i < 50; ++i) {
      prefix += count[i];
      if (prefix >= x)
        return i - 50;
    }
    return 0;
  }
}
// code provided by PROGIEZ

2653. Sliding Subarray Beauty LeetCode Solution in Python

class Solution:
  def getSubarrayBeauty(self, nums: list[int], k: int, x: int) -> list[int]:
    ans = []
    count = [0] * 50  # count[i] := the frequency of (i + 50)

    for i, num in enumerate(nums):
      if num < 0:
        count[num + 50] += 1
      if i - k >= 0 and nums[i - k] < 0:
        count[nums[i - k] + 50] -= 1
      if i + 1 >= k:
        ans.append(self._getXthSmallestNum(count, x))

    return ans

  def _getXthSmallestNum(self, count: list[int], x: int) -> int:
    prefix = 0
    for i in range(50):
      prefix += count[i]
      if prefix >= x:
        return i - 50
    return 0
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents