713. Subarray Product Less Than K

Problem Statement

link: LeetCode.cn LeetCode Given an array of integers nums and an integer k, return the number of contiguous subarrays where the product of all the elements in the subarray is strictly less than k.

Example:

Input: nums = [10,5,2,6], k = 100 Output: 8

Input: nums = [1,2,3], k = 0 Output: 0

Solution Approach

The solution utilizes a sliding window approach to count the number of contiguous subarrays where the product of elements is strictly less than the given threshold, k.

Algorithm

1. The algorithm initializes two pointers, l and r, to mark the left and right ends of the current subarray, respectively.
2. It iterates through the array, continuously expanding the window by moving the right pointer, while keeping track of the product of elements within the window.
3. If the product exceeds or equals k, the window contracts by moving the left pointer until the product falls below k again, effectively counting the number of subarrays formed where the product is less than k.

Implement

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

                

    
    

Twitter  facebook  Email