{"id":9996,"date":"2023-04-27T21:43:28","date_gmt":"2023-04-28T04:43:28","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9996"},"modified":"2023-04-27T22:02:07","modified_gmt":"2023-04-28T05:02:07","slug":"leetcode-2653-sliding-subarray-beauty","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/sliding-window\/leetcode-2653-sliding-subarray-beauty\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2653. Sliding Subarray Beauty"},"content":{"rendered":"\n<p>Given an integer array&nbsp;<code>nums<\/code>&nbsp;containing&nbsp;<code>n<\/code>&nbsp;integers, find the&nbsp;<strong>beauty<\/strong>&nbsp;of each subarray of size&nbsp;<code>k<\/code>.<\/p>\n\n\n\n<p>The&nbsp;<strong>beauty<\/strong>&nbsp;of a subarray is the&nbsp;<code>x<sup>th<\/sup><\/code><strong>&nbsp;smallest integer&nbsp;<\/strong>in the subarray if it is&nbsp;<strong>negative<\/strong>, or&nbsp;<code>0<\/code>&nbsp;if there are fewer than&nbsp;<code>x<\/code>&nbsp;negative integers.<\/p>\n\n\n\n<p>Return&nbsp;<em>an integer array containing&nbsp;<\/em><code>n - k + 1<\/code>&nbsp;<em>integers, which denote the&nbsp;<\/em><strong>beauty<\/strong><em>&nbsp;of the subarrays&nbsp;<strong>in order<\/strong>&nbsp;from the first index in the array.<\/em><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>A subarray is a contiguous&nbsp;<strong>non-empty<\/strong>&nbsp;sequence of elements within an array.<\/li><\/ul>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [1,-1,-3,-2,3], k = 3, x = 2\n<strong>Output:<\/strong> [-1,-2,-2]\n<strong>Explanation:<\/strong> There are 3 subarrays with size k = 3. \nThe first subarray is <code>[1, -1, -3]<\/code> and the 2<sup>nd<\/sup> smallest negative integer is -1.&nbsp;\nThe second subarray is <code>[-1, -3, -2]<\/code> and the 2<sup>nd<\/sup> smallest negative integer is -2.&nbsp;\nThe third subarray is <code>[-3, -2, 3]&nbsp;<\/code>and the 2<sup>nd<\/sup> smallest negative integer is -2.<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [-1,-2,-3,-4,-5], k = 2, x = 2\n<strong>Output:<\/strong> [-1,-2,-3,-4]\n<strong>Explanation:<\/strong> There are 4 subarrays with size k = 2.\nFor <code>[-1, -2]<\/code>, the 2<sup>nd<\/sup> smallest negative integer is -1.\nFor <code>[-2, -3]<\/code>, the 2<sup>nd<\/sup> smallest negative integer is -2.\nFor <code>[-3, -4]<\/code>, the 2<sup>nd<\/sup> smallest negative integer is -3.\nFor <code>[-4, -5]<\/code>, the 2<sup>nd<\/sup> smallest negative integer is -4.&nbsp;<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [-3,1,2,-3,0,-3], k = 2, x = 1\n<strong>Output:<\/strong> [-3,0,-3,-3,-3]\n<strong>Explanation:<\/strong> There are 5 subarrays with size k = 2<strong>.<\/strong>\nFor <code>[-3, 1]<\/code>, the 1<sup>st<\/sup> smallest negative integer is -3.\nFor <code>[1, 2]<\/code>, there is no negative integer so the beauty is 0.\nFor <code>[2, -3]<\/code>, the 1<sup>st<\/sup> smallest negative integer is -3.\nFor <code>[-3, 0]<\/code>, the 1<sup>st<\/sup> smallest negative integer is -3.\nFor <code>[0, -3]<\/code>, the 1<sup>st<\/sup> smallest negative integer is -3.<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>n == nums.length&nbsp;<\/code><\/li><li><code>1 &lt;= n &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>1 &lt;= k &lt;= n<\/code><\/li><li><code>1 &lt;= x &lt;= k&nbsp;<\/code><\/li><li><code>-50&nbsp;&lt;= nums[i] &lt;= 50&nbsp;<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Sliding Window + Counter<\/strong><\/h2>\n\n\n\n<p>Since the range of nums are very small (-50 ~ 50), we can use a counter to track the frequency of each element, s.t. we can find the k-the smallest element in O(50) instead of O(k).<\/p>\n\n\n\n<p>Time complexity: O((n &#8211; k + 1) * 50)<br>Space complexity: O(50)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {\n    constexpr int kMax = 50;    \n    const int n = nums.size();\n    vector<int> counts(2 * kMax + 1);\n    vector<int> ans;    \n    for (int i = 0; i < n; ++i) {\n      if (i >= k)\n        --counts[nums[i - k] + kMax];\n      ++counts[nums[i] + kMax];      \n      if (i >= k - 1) {\n        int b = 0;\n        for (int j = 0, s = 0; j <= kMax; ++j) {\n          s += counts[j];\n          if (s >= x) {\n            b = j - kMax;\n            break;\n          }\n        }\n        ans.push_back(b);\n      }\n     \n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given an integer array&nbsp;nums&nbsp;containing&nbsp;n&nbsp;integers, find the&nbsp;beauty&nbsp;of each subarray of size&nbsp;k. The&nbsp;beauty&nbsp;of a subarray is the&nbsp;xth&nbsp;smallest integer&nbsp;in the subarray if it is&nbsp;negative, or&nbsp;0&nbsp;if there are fewer&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[476],"tags":[254,177,215],"class_list":["post-9996","post","type-post","status-publish","format-standard","hentry","category-sliding-window","tag-counter","tag-medium","tag-sliding-window","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9996","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=9996"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9996\/revisions"}],"predecessor-version":[{"id":9998,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9996\/revisions\/9998"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9996"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9996"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9996"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}