Subarray Product Less Than K: Sliding Window on Products

Subarray Product Less Than K is LeetCode #713, and it is a great problem for building your intuition around the sliding window pattern. You are given an array of positive integers and a target k, and you need to count how many contiguous subarrays have a product strictly less than k. The trick is that you do not need to enumerate every subarray. A two-pointer sliding window gets the answer in a single pass.

The problem

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

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

The 8 subarrays with product less than 100 are:
[10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]

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

No subarray has a product less than 0.

The approach

The brute force way is to check every possible subarray, compute its product, and count the ones below k. That is O(n^2) work, and for arrays with up to 30,000 elements it will be too slow.

Instead, you can use a sliding window. Maintain two pointers, left and right, that define the current window. As you move right forward, multiply the running product by nums[right]. If the product becomes >= k, shrink the window from the left by dividing out nums[left] and advancing left. Once the window is valid again (product < k), every subarray ending at right and starting anywhere from left to right is also valid.

The number of such subarrays is right - left + 1. Why? Because the valid subarrays ending at index right are: [nums[right]], [nums[right-1], nums[right]], all the way to [nums[left], ..., nums[right]]. That is exactly right - left + 1 subarrays.

The solution

def numSubarrayProductLessThanK(nums, k):
    if k <= 1:
        return 0

    product = 1
    count = 0
    left = 0

    for right in range(len(nums)):
        product *= nums[right]
        while product >= k:
            product //= nums[left]
            left += 1
        count += right - left + 1

    return count

Here is what each part does:

1. Early return for k <= 1. Since all elements are positive integers (at least 1), no subarray can have a product less than 1. And a product less than 0 is impossible. So if k is 1 or smaller, the answer is always 0.

2. Initialize product = 1 and left = 0. The running product starts at 1 (the multiplicative identity), and the window starts with left at the beginning of the array.

3. Expand by moving right. For each new right, multiply the current element into the running product.

4. Shrink while invalid. If the product is >= k, divide out the leftmost element and advance left. Keep doing this until the product drops below k or the window is empty.

5. Count valid subarrays. After the window is valid, right - left + 1 gives the number of new valid subarrays ending at right. Add this to the total count.

Step-by-step walkthrough

After all four steps, the total count is 1 + 2 + 2 + 3 = 8. That matches the expected output. Notice how the left pointer only moved once (in step 3) when the product hit 100. The rest of the time, the window just kept expanding.

Complexity analysis

Time: O(n). Each element is visited at most twice: once when right moves past it, and at most once when left moves past it. The inner while loop does not make this O(n^2) because left only moves forward and never resets. Across the entire run, left moves at most n times total.

Space: O(1). You only store a few variables: product, count, left, and right. No extra arrays or hash maps needed.

The building blocks

Sliding window pattern

This problem uses the "shrinking window" variant of sliding window. You grow the window by advancing right, and you shrink it by advancing left whenever the window condition is violated (product >= k). The goal is to count all valid windows, not just find the longest or shortest one.

The same sliding window skeleton shows up in many problems:

• Minimum Size Subarray Sum uses it to find the shortest subarray with a sum at least k.
• Longest Substring Without Repeating Characters uses it to find the longest window with unique characters.
• Longest Repeating Character Replacement uses it to find the longest window where you can make all characters the same with at most k replacements.

Edge cases

• k <= 1: Since all elements are positive integers, no product can be less than 1. Return 0 immediately. This also handles k = 0 and negative values of k.
• Single element: If the array has one element and it is less than k, the answer is 1. Otherwise 0. The algorithm handles this naturally.
• All elements equal to 1: Every subarray has a product of 1. If k > 1, every subarray is valid and the answer is n * (n + 1) / 2. The sliding window never shrinks, so it counts all of them.
• Product of entire array less than k: The window expands across the whole array without ever shrinking. Every subarray is valid, and the total is again n * (n + 1) / 2.

From understanding to recall

You probably see the pattern now: expand right, shrink left while invalid, count right - left + 1. The logic is clean. But in an interview, the details trip people up. Do you divide or subtract when shrinking? Is it right - left + 1 or right - left? Do you need the k <= 1 guard?

Spaced repetition locks these details in. You write the solution from scratch today, then again tomorrow, then in a few days. After a few rounds, the while product >= k loop and the right - left + 1 counting formula are automatic. You do not need to re-derive them under pressure.

Related posts

• Minimum Size Subarray Sum - Another sliding window problem where you shrink to find the shortest valid window
• Longest Substring Without Repeating Characters - Classic sliding window with a set for tracking uniqueness
• Maximum Product Subarray - Another product-based array problem, though it uses dynamic programming instead of sliding window

If you want to build real fluency with sliding window and other patterns, CodeBricks uses spaced repetition to help you practice problems at the right intervals. Instead of grinding through hundreds of problems once, you revisit the ones that matter until the patterns stick.