⚡Flashcard Drill➔
NeetCode #245LC-713MediumSliding Window
← Back to All Problems

#245 · #713 · Subarray Product Less Than K(乘积小于 K 的子数组)

📌 Problem Statement & Constraints

Given an array of integers nums and an integer k, return the number of contiguous subarrays where the product of all elements is strictly less than k. Constraints: 1 <= nums.length <= 3 * 10^4, 1 <= nums[i] <= 1000, 0 <= k <= 10^6.

💡 Core Algorithmic Approaches

  1. All values are positive, so the product of a window is monotone in its bounds -- a sliding window applies.
  2. Expand the right end, multiplying; while the product is at least k, divide out the left element and advance.
  3. After shrinking, the window [l, r] is the longest valid window ending at r, so it contributes r - l + 1 valid subarrays.
  4. Note that k <= 1 makes the answer 0, since every element is at least 1.

💻 Benchmark Python3 Implementation

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        if k <= 1:
            return 0                   # every product is at least 1
        l = 0
        prod = 1
        res = 0
        for r, x in enumerate(nums):
            prod *= x
            while prod >= k:           # shrink until strictly less than k
                prod //= nums[l]
                l += 1
            res += r - l + 1           # all starts in the window are valid
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each element enters and leaves the window at most once.
💾 Space Complexity
O(1): two scalars.

⚠️ Interview Pitfalls & Follow-ups

  • Using prod > k instead of prod >= k: the requirement is strictly less than k.
  • Forgetting the k <= 1 guard: with k = 1 no subarray qualifies (all values are at least 1), and the shrink loop would divide by values repeatedly; the guard short-circuits it.
  • Dividing with / instead of //: integer division is required to keep the product exact.
  • Assuming zeros in the array: the constraints guarantee nums[i] >= 1, so the product never becomes zero and the window stays valid.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Sliding Window Problems