Pseudo-code:

text
count = 0
for i from 0 to n-1:
    product = 1
    for j from i to n-1:
        product = product * nums[j]
        if product < k:
            count = count + 1
        else:
            break // Optimization: Product will only grow, so stop early
return count

Complexity Analysis:

• Time Complexity: $O(N^2)$. In the worst case (e.g., all elements are 1 and $k$ is large), we iterate through all $N(N+1)/2$ subarrays.
• Space Complexity: $O(1)$.

Why it fails: While correct, the $O(N^2)$ time complexity is inefficient for the given constraints. With nums.length up to $30,000$, $N^2$ results in approximately $9 \times 10^8$ operations, which typically exceeds the time limit (usually around $10^8$ operations per second) for interview problems. We need a linear time solution.

Core Insight for Subarray Product Less Than K

The core insight relies on the relationship between a valid window and the number of valid subarrays it contains.

If a window defined by [left, right] has a product strictly less than k, then every contiguous subarray ending at right and starting at or after left also has a product less than k.

For example, if nums = [10, 5, 2] and the window is [10, 5, 2] (indices 0 to 2) with product 100:

• The subarray [10, 5, 2] ends at index 2.
• The subarray [5, 2] ends at index 2.
• The subarray [2] ends at index 2.

All of these are valid if the full window is valid. The number of such subarrays is exactly right - left + 1.

This observation allows us to count all valid subarrays ending at index right in $O(1)$ time once the valid window [left, right] is established. We do not need to iterate backwards from right.

Visual Description: Imagine a window expanding to the right by incrementing the right pointer. As we include a new number, the current_product increases. If current_product meets or exceeds k, the window is "too heavy." We must shrink the window from the left by dividing current_product by nums[left] and incrementing left. We repeat this shrinking process until the product is strictly less than k again. Once the condition is restored, the size of the current window (right - left + 1) represents the number of new valid subarrays introduced by the element at right.

Execution Flow

Let's trace nums = [10, 5, 2, 6], k = 100.

1. Initialization: left = 0, curr = 1, ans = 0.
2. right = 0 (Value 10):
   • curr becomes $1 \times 10 = 10$.
   • $10 < 100$, loop condition met.
   • Add 0 - 0 + 1 = 1 to ans. Valid subarray: [10].
   • ans is 1.
3. right = 1 (Value 5):
   • curr becomes $10 \times 5 = 50$.
   • $50 < 100$.
   • Add 1 - 0 + 1 = 2 to ans. Valid subarrays: [5], .
4. right = 2 (Value 2):
   • curr becomes $50 \times 2 = 100$.
   • $100$ is NOT strictly less than $100$.
   • Shrink: Divide by nums[0] (10). = 10. Increment to 1.
5. right = 3 (Value 6):
   • curr becomes $10 \times 6 = 60$.
   • $60 < 100$.
   • Add 3 - 1 + 1 = 3 to ans. Valid subarrays: [6], , .
6. End: Return 8.

Proof of Correctness

The algorithm correctness relies on the invariant that at the end of every iteration of the right loop, the window [left, right] represents the longest contiguous subarray ending at right with a product strictly less than k.

Because the window [left, right] is valid, any subarray starting between left and right and ending at right is also valid (due to the positive integer constraint). The number of such subarrays is right - left + 1. By summing this value at each step, we count every valid subarray exactly once—specifically, at the iteration where that subarray ends. This ensures no duplicates and no omissions.

Reference Implementation

C++ Solution for LeetCode 713

cpp
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        // Edge case: Since all nums[i] >= 1, product is always >= 1.
        // If k <= 1, no product can be strictly less than k.
        if (k <= 1) return 0;

        int left = 0;
        long long current_product = 1; // Use long long to prevent overflow
        int count = 0;

        for (int right = 0; right < nums.size(); ++right) {
            current_product *= nums[right];

            // Shrink window while product is too large
            while (current_product >= k) {
                current_product /= nums[left];
                left++;
            }

            // Add the number of valid subarrays ending at 'right'
            count += (right - left + 1);
        }

        return count;
    }
};

Java Solution for LeetCode 713

java
class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        // Edge case: Since elements are >= 1, product is >= 1.
        // If k <= 1, strictly less than k is impossible.
        if (k <= 1) return 0;

        int left = 0;
        long currentProduct = 1;
        int count = 0;

        for (int right = 0; right < nums.length; right++) {
            currentProduct *= nums[right];

            // Shrink the window from the left if constraint is violated
            while (currentProduct >= k) {
                currentProduct /= nums[left];
                left++;
            }

            // All subarrays ending at 'right' within the window are valid
            count += (right - left + 1);
        }

        return count;
    }
}

Python Solution for LeetCode 713

python
class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        # Edge case: If k <= 1, no subarray product (>=1) can be < k
        if k <= 1:
            return 0
        
        left = 0
        current_product = 1
        count = 0
        
        for right in range(len(nums)):
            current_product *= nums[right]
            
            # Shrink window while product is invalid
            while current_product >= k:
                current_product //= nums[left]
                left += 1
            
            # Add count of valid subarrays ending at current right
            count += (right - left + 1)
            
        return count

Q: Why does my code return a non-zero answer when k = 0 or k = 1? Mistake: Failing to handle k <= 1. Why: The problem states elements are positive integers. Thus, the minimum product is 1. If k is 0 or 1, no product can be strictly less than k. Without an explicit check, the logic right - left + 1 might erroneously add counts if the while loop logic isn't perfectly robust against empty windows. Consequence: Incorrect output for edge cases.

Q: Why is my answer slightly off (e.g., missing some subarrays)? Mistake: Incorrectly calculating the number of subarrays. Why: A common error is adding 1 (just the current element) instead of right - left + 1. Consequence: This counts only single-element subarrays or fails to account for valid longer subarrays ending at the current index.

Q: Why do I get division by zero errors? Mistake: Assuming the window is non-empty before dividing. Why: In rare logic structures (specifically if not handling k <= 1), the while loop might run until left > right. If you try to access nums[left] when left is out of bounds or divide when the product is effectively reset, it causes errors. Consequence: Runtime errors. The standard pattern logic prevents this if k <= 1 is handled first.