Welcome to Subscribe On Youtube
2653. Sliding Subarray Beauty
Description
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.length1 <= n <= 1051 <= k <= n1 <= x <= k-50 <= nums[i] <= 50
Solutions
-
class Solution { public int[] getSubarrayBeauty(int[] nums, int k, int x) { int n = nums.length; int[] cnt = new int[101]; for (int i = 0; i < k; ++i) { ++cnt[nums[i] + 50]; } int[] ans = new int[n - k + 1]; ans[0] = f(cnt, x); for (int i = k, j = 1; i < n; ++i) { ++cnt[nums[i] + 50]; --cnt[nums[i - k] + 50]; ans[j++] = f(cnt, x); } return ans; } private int f(int[] cnt, int x) { int s = 0; for (int i = 0; i < 50; ++i) { s += cnt[i]; if (s >= x) { return i - 50; } } return 0; } } -
class Solution { public: vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) { int n = nums.size(); int cnt[101]{}; for (int i = 0; i < k; ++i) { ++cnt[nums[i] + 50]; } vector<int> ans(n - k + 1); auto f = [&](int x) { int s = 0; for (int i = 0; i < 50; ++i) { s += cnt[i]; if (s >= x) { return i - 50; } } return 0; }; ans[0] = f(x); for (int i = k, j = 1; i < n; ++i) { ++cnt[nums[i] + 50]; --cnt[nums[i - k] + 50]; ans[j++] = f(x); } return ans; } }; -
from sortedcontainers import SortedList class Solution: def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]: sl = SortedList(nums[:k]) ans = [sl[x - 1] if sl[x - 1] < 0 else 0] for i in range(k, len(nums)): sl.remove(nums[i - k]) sl.add(nums[i]) ans.append(sl[x - 1] if sl[x - 1] < 0 else 0) return ans -
func getSubarrayBeauty(nums []int, k int, x int) []int { n := len(nums) cnt := [101]int{} for _, x := range nums[:k] { cnt[x+50]++ } ans := make([]int, n-k+1) f := func(x int) int { s := 0 for i := 0; i < 50; i++ { s += cnt[i] if s >= x { return i - 50 } } return 0 } ans[0] = f(x) for i, j := k, 1; i < n; i, j = i+1, j+1 { cnt[nums[i]+50]++ cnt[nums[i-k]+50]-- ans[j] = f(x) } return ans } -
function getSubarrayBeauty(nums: number[], k: number, x: number): number[] { const n = nums.length; const cnt: number[] = new Array(101).fill(0); for (let i = 0; i < k; ++i) { ++cnt[nums[i] + 50]; } const ans: number[] = new Array(n - k + 1); const f = (x: number): number => { let s = 0; for (let i = 0; i < 50; ++i) { s += cnt[i]; if (s >= x) { return i - 50; } } return 0; }; ans[0] = f(x); for (let i = k, j = 1; i < n; ++i, ++j) { cnt[nums[i] + 50]++; cnt[nums[i - k] + 50]--; ans[j] = f(x); } return ans; } -
class MedianFinder { private PriorityQueue<Integer> small = new PriorityQueue<>(Comparator.reverseOrder()); private PriorityQueue<Integer> large = new PriorityQueue<>(); private Map<Integer, Integer> delayed = new HashMap<>(); private int smallSize; private int largeSize; private int x; public MedianFinder(int x) { this.x = x; } public void addNum(int num) { if (smallSize < x || num <= small.peek()) { small.offer(num); ++smallSize; } else { large.offer(num); ++largeSize; } rebalance(); } public int find() { return smallSize == x ? small.peek() : 0; } public void removeNum(int num) { delayed.merge(num, 1, Integer::sum); if (num <= small.peek()) { --smallSize; if (num == small.peek()) { prune(small); } } else { --largeSize; if (num == large.peek()) { prune(large); } } rebalance(); } private void prune(PriorityQueue<Integer> pq) { while (!pq.isEmpty() && delayed.containsKey(pq.peek())) { if (delayed.merge(pq.peek(), -1, Integer::sum) == 0) { delayed.remove(pq.peek()); } pq.poll(); } } private void rebalance() { if (smallSize > x) { large.offer(small.poll()); --smallSize; ++largeSize; prune(small); } else if (smallSize < x && largeSize > 0) { small.offer(large.poll()); --largeSize; ++smallSize; prune(large); } } } class Solution { public int[] getSubarrayBeauty(int[] nums, int k, int x) { MedianFinder finder = new MedianFinder(x); for (int i = 0; i < k; ++i) { if (nums[i] < 0) { finder.addNum(nums[i]); } } int n = nums.length; int[] ans = new int[n - k + 1]; ans[0] = finder.find(); for (int i = k; i < n; ++i) { if (nums[i] < 0) { finder.addNum(nums[i]); } if (nums[i - k] < 0) { finder.removeNum(nums[i - k]); } ans[i - k + 1] = finder.find(); } return ans; } } -
class MedianFinder { public: MedianFinder(int x) { this->x = x; } void addNum(int num) { if (smallSize < x || num <= small.top()) { small.push(num); ++smallSize; } else { large.push(num); ++largeSize; } reblance(); } void removeNum(int num) { ++delayed[num]; if (num <= small.top()) { --smallSize; if (num == small.top()) { prune(small); } } else { --largeSize; if (num == large.top()) { prune(large); } } reblance(); } int find() { return smallSize == x ? small.top() : 0; } private: priority_queue<int> small; priority_queue<int, vector<int>, greater<int>> large; unordered_map<int, int> delayed; int smallSize = 0; int largeSize = 0; int x; template <typename T> void prune(T& pq) { while (!pq.empty() && delayed[pq.top()]) { if (--delayed[pq.top()] == 0) { delayed.erase(pq.top()); } pq.pop(); } } void reblance() { if (smallSize > x) { large.push(small.top()); small.pop(); --smallSize; ++largeSize; prune(small); } else if (smallSize < x && largeSize > 0) { small.push(large.top()); large.pop(); ++smallSize; --largeSize; prune(large); } } }; class Solution { public: vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) { MedianFinder finder(x); for (int i = 0; i < k; ++i) { if (nums[i] < 0) { finder.addNum(nums[i]); } } int n = nums.size(); vector<int> ans; ans.push_back(finder.find()); for (int i = k; i < n; ++i) { if (nums[i] < 0) { finder.addNum(nums[i]); } if (nums[i - k] < 0) { finder.removeNum(nums[i - k]); } ans.push_back(finder.find()); } return ans; } }; -
class MedianFinder: def __init__(self, x: int): self.x = x self.small = [] self.large = [] self.delayed = defaultdict(int) self.small_size = 0 self.large_size = 0 def add_num(self, num: int): if self.small_size < self.x or num <= -self.small[0]: heappush(self.small, -num) self.small_size += 1 else: heappush(self.large, num) self.large_size += 1 self.rebalance() def find(self) -> float: return -self.small[0] if self.small_size == self.x else 0 def remove_num(self, num: int): self.delayed[num] += 1 if num <= -self.small[0]: self.small_size -= 1 if num == -self.small[0]: self.prune(self.small) else: self.large_size -= 1 if num == self.large[0]: self.prune(self.large) self.rebalance() def prune(self, pq: List[int]): sign = -1 if pq is self.small else 1 while pq and sign * pq[0] in self.delayed: self.delayed[sign * pq[0]] -= 1 if self.delayed[sign * pq[0]] == 0: self.delayed.pop(sign * pq[0]) heappop(pq) def rebalance(self): if self.small_size > self.x: heappush(self.large, -heappop(self.small)) self.small_size -= 1 self.large_size += 1 self.prune(self.small) elif self.small_size < self.x and self.large_size > 0: heappush(self.small, -heappop(self.large)) self.large_size -= 1 self.small_size += 1 self.prune(self.large) class Solution: def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]: finder = MedianFinder(x) for i in range(k): if nums[i] < 0: finder.add_num(nums[i]) ans = [finder.find()] for i in range(k, len(nums)): if nums[i] < 0: finder.add_num(nums[i]) if nums[i - k] < 0: finder.remove_num(nums[i - k]) ans.append(finder.find()) return ans -
type MedianFinder struct { small hp large hp delayed map[int]int smallSize, largeSize int x int } func Constructor(x int) MedianFinder { return MedianFinder{hp{}, hp{}, map[int]int{}, 0, 0, x} } func (this *MedianFinder) AddNum(num int) { if this.smallSize < this.x || num <= -this.small.IntSlice[0] { heap.Push(&this.small, -num) this.smallSize++ } else { heap.Push(&this.large, num) this.largeSize++ } this.rebalance() } func (this *MedianFinder) Find() int { if this.smallSize == this.x { return -this.small.IntSlice[0] } return 0 } func (this *MedianFinder) RemoveNum(num int) { this.delayed[num]++ if num <= -this.small.IntSlice[0] { this.smallSize-- if num == -this.small.IntSlice[0] { this.prune(&this.small) } } else { this.largeSize-- if num == this.large.IntSlice[0] { this.prune(&this.large) } } this.rebalance() } func (this *MedianFinder) prune(pq *hp) { sign := 1 if pq == &this.small { sign = -1 } for pq.Len() > 0 && this.delayed[sign*pq.IntSlice[0]] > 0 { this.delayed[sign*pq.IntSlice[0]]-- if this.delayed[sign*pq.IntSlice[0]] == 0 { delete(this.delayed, sign*pq.IntSlice[0]) } heap.Pop(pq) } } func (this *MedianFinder) rebalance() { if this.smallSize > this.x { heap.Push(&this.large, -heap.Pop(&this.small).(int)) this.smallSize-- this.largeSize++ this.prune(&this.small) } else if this.smallSize < this.x && this.largeSize > 0 { heap.Push(&this.small, -heap.Pop(&this.large).(int)) this.smallSize++ this.largeSize-- this.prune(&this.large) } } type hp struct{ sort.IntSlice } func (h hp) Less(i, j int) bool { return h.IntSlice[i] < h.IntSlice[j] } func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) } func (h *hp) Pop() any { a := h.IntSlice v := a[len(a)-1] h.IntSlice = a[:len(a)-1] return v } func getSubarrayBeauty(nums []int, k int, x int) []int { finder := Constructor(x) for _, num := range nums[:k] { if num < 0 { finder.AddNum(num) } } ans := []int{finder.Find()} for i := k; i < len(nums); i++ { if nums[i] < 0 { finder.AddNum(nums[i]) } if nums[i-k] < 0 { finder.RemoveNum(nums[i-k]) } ans = append(ans, finder.Find()) } return ans }