Devin's Blog

Subarray Product Less Than K

3 min read

Related: Minimum Size Subarray Sum

Intuition

  • I started this problem by attempting a nested for loop approach, which got a TLE.
  • I then did a Backtracking based approach in which I went backwards from the last element and passed computations up to the first index, which also got TLE since I am essentially doing the same thing as a double for loop but recursively.
  • I then solved Minimum Size Subarray Sum which helped me understand why we must use right - left + 1 format, since left can be past right by one, but right will catch up immediately after due to the for loop, as opposed to my Original which required right - left.
  • The main point of this problem is that you multiply the product, and then when you reach a point where your window contains a product k, you slide from left to right until your window contains a product less than k. Once you have done that, instead of recursively starting from the left + 1 index of that array and counting the number of subarrays, you can do right - left + 1, which essentially takes the size of your window which is how many there would be in the first place.
    • For example, if you have [5,2,6], then you would have to take [5], [5,2], [2], [2,6], and [6] = 5 count, but instead you do 3 + 2 since you would find 3 on the first and 2 on the 2nd iteration of [2,6].

Note

This only works when numbers are positive and all integers.

Complexity

Runtime

(N + N) with Sliding Window since you have at most N divisions of prod and N iterations of the outer for loop.

Space

due to just axillary variables

Code

Sliding Window

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

Backtracking (TLE)

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        n = len(nums)
        count = 0
        def r(index):
            nonlocal count
            if index >= n:
                return deque([])
 
            cur = nums[index]
            if cur >= k:
                return deque([])
            count += 1
 
            cur_products = deque([cur])
            old_products = r(index + 1)
            for _ in range(len(old_products)):
                computation = cur * old_products.popleft()
                if computation >= k:
                    break
                count += 1
                cur_products.append(computation)
            return cur_products
 
        r(0)
        return count

Iterative (TLE)

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        count = 0
        for i, num in enumerate(nums):
            cur = []
            product = 1
            for j in range(i, len(nums)):
                product *= nums[j]
                if product >= k:
                    break
                cur.append(nums[j])
                count += 1
        return count

Notes

References

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

Graph View