Skip to content

2653. Sliding Subarray Beauty 👍

  • Time: $O(50n) = O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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