Sliding Window Variable Subarrays Shorter¶
Table of Contents¶
- 713. Subarray Product Less Than K (Medium)
- 3258. Count Substrings That Satisfy K-Constraint I (Easy)
- 2302. Count Subarrays With Score Less Than K (Hard)
- 2762. Continuous Subarrays (Medium)
- 3134. Find the Median of the Uniqueness Array (Hard)
- 3261. Count Substrings That Satisfy K-Constraint II (Hard)
- 2743. Count Substrings Without Repeating Character (Medium) 👑
713. Subarray Product Less Than K¶
from typing import List
# Sliding Window Variable Subarrays Shorter
def numSubarrayProductLessThanK(nums: List[int], k: int) -> int:
if k <= 1:
return 0
left = 0
prod = 1
res = 0
for right in range(len(nums)):
prod *= nums[right]
while prod >= k:
prod //= nums[left]
left += 1
res += right - left + 1
return res
if __name__ == "__main__":
assert numSubarrayProductLessThanK([10, 5, 2, 6], 100) == 8
assert numSubarrayProductLessThanK([1, 2, 3], 0) == 0
assert numSubarrayProductLessThanK([1, 2, 3], 1) == 0
assert numSubarrayProductLessThanK([1, 2, 3], 2) == 1
assert numSubarrayProductLessThanK([1, 2, 3], 3) == 3
3258. Count Substrings That Satisfy K-Constraint I¶
2302. Count Subarrays With Score Less Than K¶
2762. Continuous Subarrays¶
-
Tags: Array, Queue, Sliding Window, Heap Priority Queue, Ordered Set, Monotonic Queue