Subarray Product Less Than K

Problem

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

Constraints

• 1 ≤ nums.length ≤ 30000
• 1 ≤ nums[i] ≤ 1000
• 0 ≤ k ≤ 1000000

Approach — Sliding Window

This is a Sliding Window problem. The idea: keep a moving window over the sequence, expanding and shrinking it while tracking the answer in a single pass. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time.

Solution code

Python

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

Java

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;
        int prod = 1, left = 0, count = 0;
        for (int right = 0; right < nums.length; right++) {
            prod *= nums[right];
            // Shrink until the window product drops below k.
            while (prod >= k) {
                prod /= nums[left];
                left++;
            }
            // Every subarray ending at right and starting in [left..right] counts.
            count += right - left + 1;
        }
        return count;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.