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

• LeetCode | LeetCode CH (Medium)

• Tags: array, binary search, sliding window, prefix sum

713. Subarray Product Less Than K - Python Solution

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

• LeetCode | LeetCode CH (Easy)

• Tags: string, sliding window

2302. Count Subarrays With Score Less Than K

• LeetCode | LeetCode CH (Hard)

• Tags: array, binary search, sliding window, prefix sum

2762. Continuous Subarrays

• LeetCode | LeetCode CH (Medium)

• Tags: array, queue, sliding window, heap priority queue, ordered set, monotonic queue

3134. Find the Median of the Uniqueness Array

• LeetCode | LeetCode CH (Hard)

• Tags: array, hash table, binary search, sliding window

3261. Count Substrings That Satisfy K-Constraint II

• LeetCode | LeetCode CH (Hard)

• Tags: array, string, binary search, sliding window, prefix sum

2743. Count Substrings Without Repeating Character

• LeetCode | LeetCode CH (Medium)

• Tags: hash table, string, sliding window

Comments