713. Subarray Product Less Than k

url: https://leetcode.com/problems/subarray-product-less-than-k/description/

Input: nums = [10, 5, 2, 6], k = 100
Output: 8
Explanation:
  [10]
  [5]
  [2]
  [6]
  [10, 5] = 50
  [5, 2] = 10
  [2, 6] = 12
  [5, 2, 6] = 60
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.

💻 Code

1. Solution

Sliding Window

• TC: $O(n)$
• SC: $O(1)$
  

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        ans = 0
        left = 0 # left starts from the index 0
        prod = 1

        # slide the window with conditions
        for right, num in enumerate(nums):
            prod *= num
            # if product of current window larget than k
            if prod >= k and left <= right:
                # move the left pointer!
                prod //= nums[left]
                left += 1
            # current window less than k
            ans += right - left + 1
        return ans

In this solution, two pointers (left & right) are needed to set the window up, and it allows us to apply conditions as needed. For the right pointer, it will access the next index if the product of the current window satisfies the condition, which is less than K. In other words, the left pointer will be moved if it is larger than K to shrink and find the appropriate window.

The Most important thing in this logic is to count the valid number of subarrays using right - left + 1 so that we don’t have to go over the subarray to find a valid combination within the window again.
Let’s think simple! If the window is valid, its subarrays are already verified to meet the condition.

Why +1 ?
Since we extends the right pointer, we should also calculate the new right pointer num itself!