Subarray Product Less Than K — LC 713 Sliding Window Deep Dive

Problem Statement#

Given an array of positive integers nums and an integer k, count contiguous subarrays whose product is strictly less than k.

Constraints:

• 1 less than or equal to nums.length less than or equal to 3 times 10 to the 4
• 1 less than or equal to nums[i] less than or equal to 1000
• 0 less than or equal to k less than or equal to 10 to the 6

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

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

Why This Problem Matters#

LeetCode 713 — Subarray Product Less Than K is a high-frequency Google, Amazon, and Stripe interview question that tests whether you can adapt the sliding window technique from sums to products. Most candidates know the additive sliding window for "longest subarray with sum at most k," but they freeze when the operation changes. Interviewers exploit that gap to differentiate between candidates who memorized templates and those who understand the underlying monotonic invariant.

The counting twist — return the number of valid subarrays rather than the longest length — also shows up in LC 992 (Subarrays with K Different Integers) and LC 1248 (Count Number of Nice Subarrays). Mastering the right - left + 1 counting trick here pays dividends across the entire two-pointer category.

In production systems, this pattern maps directly to anomaly windows, fraud detection over rolling transaction products, and ranking signals where you multiply weights instead of adding them.

The Core Insight#

Because all values are positive, the running product is monotonically non-decreasing as right extends and non-increasing as left advances. That monotonicity is the prerequisite for a valid sliding window.

For each new right, shrink the window by advancing left while product is greater than or equal to k. Once the window is valid, every subarray ending at right and starting at any index in [left, right] is valid. That gives right - left + 1 new subarrays in this iteration. Summing this count across all right positions yields the total in O(n).

The off-by-one trap: dividing the leftmost element out when shrinking. Because we are working with integer products and floor division is fine when values are positive, exact integer divides reverse the multiplication cleanly.

Visual Dry Run#

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

Final answer: 8 valid subarrays.

Solution (Optimal)#

class Solution:
    def numSubarrayProductLessThanK(self, nums, k):
        if k <= 1:
            return 0
        product, left, count = 1, 0, 0
        for right, value in enumerate(nums):
            product *= value
            while product >= k:
                product //= nums[left]
                left += 1
            count += right - left + 1
        return count

var numSubarrayProductLessThanK = function(nums, k) {
    if (k <= 1) return 0;
    let product = 1, left = 0, count = 0;
    for (let right = 0; right < nums.length; right++) {
        product *= nums[right];
        while (product >= k) {
            product = Math.floor(product / nums[left]);
            left++;
        }
        count += right - left + 1;
    }
    return count;
};

Time: O(n) — each index enters and leaves the window once. Space: O(1) — only running product and indices.

Common Mistakes#

• Forgetting the k less than or equal to 1 guard. With positive integers the smallest product is 1, so no subarray qualifies and the loop would underflow.
• Using less than or equal to instead of strict less than when comparing the product. The problem requires strictly less than k.
• Counting subarrays as right - left instead of right - left + 1. The window is inclusive on both ends.
• Trying to undo a multiplication with subtraction. Use integer division because all values are positive.
• Applying the same template when negatives or zeros are allowed — the monotonicity assumption breaks.

Interview Tips#

• Call out the positivity precondition on whiteboard before coding.
• Explain the counting trick: every subarray ending at right and starting in [left, right] is valid.
• Walk through what happens when a single element is greater than or equal to k so the interviewer sees you handle the shrink-to-empty case.
• Compare with the additive version to show pattern transfer.
• Mention the k less than or equal to 1 early return as a safety guard.

Follow-up Questions#

• How do you handle zeros in the array? Reset the product on zero and treat the next index as a fresh window.
• What if negatives are allowed? Sliding window fails; switch to prefix products plus a sorted multiset.
• Count subarrays with product greater than or equal to k. Total subarrays minus the answer here.
• Find the maximum length instead of count. Track right - left + 1 and keep the best.
• Same problem on streaming data. Maintain a deque of recent values and amortize the shrink.

Key Takeaways#

• LeetCode 713 — Subarray Product Less Than K runs in O(n) time and O(1) space.
• Positive values make running product monotonic, which is the contract for a valid sliding window.
• Counting trick: each valid window contributes right - left + 1 new subarrays.
• Strictly less than means use less than, not less than or equal to.
• The k less than or equal to 1 guard prevents underflow on edge cases.
• Google, Amazon, and Stripe ask this problem in their final-loop array screens.
• The same template extends to LC 992, LC 1248, and any subarray-count problem with monotonic windows.