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
- All values are positive, so the product of a window is monotone in its bounds -- a sliding window applies.
- Expand the right end, multiplying; while the product is at least
k, divide out the left element and advance. - After shrinking, the window
[l, r]is the longest valid window ending atr, so it contributesr - l + 1valid subarrays. - Note that
k <= 1makes 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 > kinstead ofprod >= k: the requirement is strictly less thank. - Forgetting the
k <= 1guard: withk = 1no 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.
🧩 Related Sliding Window Problems
#219 · #219Contains Duplicate II#220 · #121Best Time to Buy and Sell Stock#221 · #2379Minimum Recolors to Get K Consecutive Black Blocks#222 · #1984Minimum Difference Between Highest and Lowest of K Scores#223 · #1343Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold#224 · #1052Grumpy Bookstore Owner