LeetCode 713 - Subarray Product Less Than K

The problem asks us to count how many contiguous subarrays of a given array have a product strictly smaller than a target value k. A subarray is a continuous portion of the array.

leetcodemediumarraybinary-searchsliding-windowprefix-sum

LeetCode Problem 713

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Sliding Window, Prefix Sum

Solution

Problem Understanding

The problem asks us to count how many contiguous subarrays of a given array have a product strictly smaller than a target value k.

A subarray is a continuous portion of the array. For example, in the array [10, 5, 2, 6], the subarray [5, 2] is valid because those elements appear consecutively, while [10, 2] is not a valid subarray because the elements are separated.

The input consists of:

  • nums, an array of positive integers
  • k, an integer threshold

For every possible contiguous subarray, we compute the product of all elements inside it. If that product is strictly less than k, the subarray contributes to the final count.

The important detail is that the condition is strictly less than k, not less than or equal to k.

The constraints are important because they determine which algorithms are feasible:

  • nums.length can be as large as 3 * 10^4
  • Each element is positive, between 1 and 1000
  • k can be as large as 10^6

A naive algorithm that checks every subarray explicitly would require quadratic time, which becomes too slow when the array length approaches 30,000.

A very important property is that all numbers are positive. This completely changes the behavior of the product when expanding or shrinking a window:

  • Multiplying by a new positive number can only increase or maintain the product
  • Dividing by a removed positive number can only decrease or maintain the product

This monotonic behavior makes the sliding window technique possible.

Several edge cases are important:

  • If k <= 1, the answer is always 0, because every element in nums is at least 1, so every subarray product is at least 1
  • Arrays containing many 1s can produce a large number of valid subarrays
  • Large products may temporarily exceed k, requiring repeated shrinking of the window
  • Single-element subarrays must also be counted

Approaches

Brute Force Approach

The most direct solution is to generate every possible subarray and compute its product.

For each starting index i, we extend the subarray one element at a time toward the right:

  • Start with product 1
  • Multiply by nums[j] for every ending index j >= i
  • If the product is less than k, increment the answer

This approach is correct because it explicitly examines every contiguous subarray exactly once.

However, the number of subarrays in an array of length n is:

$$\frac{n(n+1)}{2}$$

which is O(n^2).

With n = 30000, this becomes far too slow.

Optimal Sliding Window Approach

The key observation is that all elements are positive.

Suppose we maintain a window [left, right] whose product is less than k.

If we extend the window by moving right forward, the product can only increase because all values are positive.

If the product becomes too large, we can restore validity by moving left forward and dividing out elements from the product.

The crucial insight is this:

If the current window [left, right] has product less than k, then every subarray ending at right and starting anywhere between left and right is also valid.

For example, if:

[left ... right]

is valid, then these are also valid:

[right]
[right-1 ... right]
[right-2 ... right]
...
[left ... right]

The number of such subarrays is:

right - left + 1

This allows us to count many valid subarrays at once instead of checking them individually.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Checks every subarray explicitly
Optimal O(n) O(1) Uses sliding window with shrinking left boundary

Algorithm Walkthrough

Step 1: Handle the special case k <= 1

Since every element in nums is at least 1, every subarray product is also at least 1.

That means no subarray can satisfy:

$$\text{product} < k$$

when k <= 1.

So we immediately return 0.

Step 2: Initialize the sliding window

We maintain:

  • left, the left boundary of the window
  • product, the product of all elements inside the window
  • count, the total number of valid subarrays found so far

Initially:

  • left = 0
  • product = 1
  • count = 0

Step 3: Expand the window to the right

We iterate through the array using right.

For each new element:

  • Multiply it into the current product
  • The window now becomes [left, right]

Step 4: Shrink the window while the product is too large

If the product becomes greater than or equal to k, the current window is invalid.

We repeatedly:

  • Divide out nums[left]
  • Move left one step right

until the product becomes valid again.

Because all numbers are positive, shrinking the window always decreases or maintains the product.

Step 5: Count valid subarrays ending at right

Once the window is valid again, every subarray ending at right and starting between left and right is valid.

The number of such subarrays is:

$$right - left + 1$$

We add this value to the answer.

Step 6: Continue until the array is exhausted

We repeat the process for every position of right.

At the end, count contains the total number of valid subarrays.

Why it works

The algorithm maintains the invariant that the current window [left, right] always has product strictly less than k.

Because all values are positive, removing elements from the left can only decrease the product. Therefore, once the window becomes valid again, every smaller suffix inside that window is also valid.

For a fixed right, the algorithm counts exactly all valid subarrays ending at right, and no subarray is counted more than once. This guarantees correctness.

Python Solution

from typing import List

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        if k <= 1:
            return 0

        left = 0
        product = 1
        count = 0

        for right in range(len(nums)):
            product *= nums[right]

            while product >= k:
                product //= nums[left]
                left += 1

            count += right - left + 1

        return count

The implementation begins with the critical edge-case check for k <= 1. Without this condition, the sliding window logic would fail because no valid subarray could ever exist.

The variable product stores the current window product. As the right pointer expands the window, the new value is multiplied into the product.

Whenever the product becomes invalid, the while loop shrinks the window from the left side until the product is once again strictly less than k.

After restoring validity, the expression:

right - left + 1

counts all valid subarrays ending at index right.

The algorithm never revisits elements unnecessarily. Each element enters the window once and leaves the window once, which is why the total runtime is linear.

Go Solution

func numSubarrayProductLessThanK(nums []int, k int) int {
    if k <= 1 {
        return 0
    }

    left := 0
    product := 1
    count := 0

    for right := 0; right < len(nums); right++ {
        product *= nums[right]

        for product >= k {
            product /= nums[left]
            left++
        }

        count += right - left + 1
    }

    return count
}

The Go implementation follows the same logic as the Python solution.

One important detail is integer division. Since every value being divided was previously multiplied into the product, integer division remains exact.

Go slices are already reference-like structures, so no additional copying is required.

The constraints guarantee that standard integer arithmetic is sufficient for this problem.

Worked Examples

Example 1

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

Initial state:

left = 0
product = 1
count = 0
right nums[right] product after multiply Window After Shrink Valid Subarrays Added count
0 10 10 [10] 1 1
1 5 50 [10,5] 2 3
2 2 100 shrink to [5,2] with product 10 2 5
3 6 60 [5,2,6] 3 8

Detailed reasoning:

When right = 3, the valid subarrays ending at index 3 are:

[6]
[2,6]
[5,2,6]

which gives 3 additional subarrays.

Final answer:

8

Example 2

nums = [1,2,3]
k = 0

Since k <= 1, no valid subarray can exist.

Every product is at least 1.

The algorithm immediately returns:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element enters and leaves the window at most once
Space O(1) Only a few variables are used

Although there is a nested while loop, the total number of left-pointer movements across the entire algorithm is at most n. This means the total work remains linear.

The algorithm uses constant extra memory because it only stores indices, a running product, and the final count.

Test Cases

from typing import List

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        if k <= 1:
            return 0

        left = 0
        product = 1
        count = 0

        for right in range(len(nums)):
            product *= nums[right]

            while product >= k:
                product //= nums[left]
                left += 1

            count += right - left + 1

        return count

sol = Solution()

assert sol.numSubarrayProductLessThanK([10,5,2,6], 100) == 8  # provided example
assert sol.numSubarrayProductLessThanK([1,2,3], 0) == 0  # k is zero
assert sol.numSubarrayProductLessThanK([1], 2) == 1  # single valid element
assert sol.numSubarrayProductLessThanK([5], 5) == 0  # strict inequality
assert sol.numSubarrayProductLessThanK([1,1,1], 2) == 6  # all subarrays valid
assert sol.numSubarrayProductLessThanK([1000,1000], 1000000) == 2  # large values
assert sol.numSubarrayProductLessThanK([2,3,4], 25) == 5  # shrinking window needed
assert sol.numSubarrayProductLessThanK([1,2,3], 1) == 0  # k equals one
assert sol.numSubarrayProductLessThanK([10,9,10,4,3,8,3,3,6,2,10,10,9,3], 19) == 18  # stress-style mixed case
Test Why
[10,5,2,6], k=100 Standard example with multiple valid windows
[1,2,3], k=0 Verifies k <= 1 handling
[1], k=2 Smallest valid input
[5], k=5 Confirms strict inequality behavior
[1,1,1], k=2 Every subarray should be valid
[1000,1000], k=1000000 Large products near threshold
[2,3,4], k=25 Requires repeated shrinking
[1,2,3], k=1 Another impossible-case scenario
Large mixed input General stress and correctness validation

Edge Cases

Case 1: k <= 1

This is the most important edge case in the entire problem.

Since all numbers are positive integers and at least 1, every subarray product is also at least 1.

Therefore, when k is 0 or 1, no valid subarray can exist.

A common bug is forgetting this condition, which can lead to incorrect counting or infinite shrinking loops. The implementation handles this immediately with:

if k <= 1:
    return 0

Case 2: Single-element arrays

Arrays containing only one element are easy to mishandle if the algorithm assumes larger windows.

For example:

nums = [5], k = 10

The single subarray [5] is valid.

The sliding window naturally handles this because the window size can remain 1, and the formula:

right - left + 1

correctly evaluates to 1.

Case 3: Products that repeatedly exceed k

Some inputs require shrinking the window multiple times in succession.

Example:

nums = [2,3,4]
k = 10

When the product becomes 24, removing only one element may still leave the product too large.

The while loop is essential because it continues shrinking until the invariant is restored:

while product >= k:
    product //= nums[left]
    left += 1

Without the loop, the algorithm would incorrectly count invalid subarrays.