MediumNo. 2653
Sliding Subarray Beauty — LeetCode 2653 Python Solution
- Pattern
- Sliding Window
- Topics
- Array, Hash Table, Sliding Window
- Reading time
- 4 min
- Source
- leetcode.com
The problem
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.
Example
- Input
- nums = [1,-1,-3,-2,3], k = 3, x = 2
- Output
- [-1,-2,-2]
- Explanation
- There are 3 subarrays with size k = 3.
Python solution
class Solution:
def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:
def f(x: int) -> int:
s = 0
for i in range(50):
s += cnt[i]
if s >= x:
return i - 50
return 0
cnt = [0] * 101
for v in nums[:k]:
cnt[v + 50] += 1
ans = [f(x)]
for i in range(k, len(nums)):
cnt[nums[i] + 50] += 1
cnt[nums[i - k] + 50] -= 1
ans.append(f(x))
return ansComplexity
- Time
- O(n × 50)
- Space · auxiliary
- O(100)
Pattern: Sliding Window
Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 2653. Sliding Subarray Beauty is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.
The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0219 | Contains Duplicate II | Easy |
| 0480 | Sliding Window Median | Hard |
| 0594 | Longest Harmonious Subsequence | Easy |
| 0632 | Smallest Range Covering Elements from K Lists | Hard |
| 0904 | Fruit Into Baskets | Medium |
| 0930 | Binary Subarrays With Sum | Medium |
Frequently asked questions
- How hard is LeetCode 2653. Sliding Subarray Beauty?
LeetCode 2653. Sliding Subarray Beauty is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2653. Sliding Subarray Beauty?
The Python solution on this page runs in O(n × 50).
- What is the space complexity of LeetCode 2653. Sliding Subarray Beauty?
The Python solution on this page uses O(100) auxiliary space.
- What topics does LeetCode 2653. Sliding Subarray Beauty cover?
LeetCode 2653. Sliding Subarray Beauty is tagged Array, Hash Table and Sliding Window on LeetCode.