713. Subarray Product Less Than K

[box-lin]

Sliding Window Approach

Constrain

• 1 <= nums.length <= 3 * 10^4
• 1 <= nums[i] <= 1000
• 0 <= k <= 10^6

Analysis

• Time: O(n)
• Space: O(1)

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        n = len(nums)
        l = 0 
        p = 1
        ans = 0
        for r in range(n):
            p = p * nums[r]
            while p >= k and l <= r:
                p = p // nums[l]
                l += 1
            ans += r-l+1
        return ans

Note

• A window is maintained such that the product of the window is less than k.
• r-l+1 is the trickier part. $Proof$ $Suppose \ we've\ known \ numbers \ of \ valid \ subarrays \ X \ whose \ product \ is \ less \ than \ k \ in \ subarray\ [1,2]\ $ $Now \ for \ an \ subarray \ [1,2,3] \ whose\ product \ is \ still \ less \ than \ k$ $We \ just \ need \ to \ add \ numbers \ of \ subarray \ ends \ with \ 3 \ that \ is \ [1,2,3],[2,3], [3] \ which \ r=2, \ l=0 \ $ $2-0+1 = 3, so\ total \ is \ X+3\ $ $X\ obviously \ is \ 3, [1],[2],[1,2] \ so \ ans \ = 3+3=6$

[Lstsk]

Hello test

[wantingw]

🤔