Count Subarrays With Product Less Than K

Medium20–25 min

Topics

ArraySliding Window

Companies

AmazonGoogleMicrosoftBloomberg

Given an array of positive integers nums and an integer k, count the number of contiguous subarrays whose product of all elements is strictly less than k. Checking every subarray directly works but repeats the same multiplications across overlapping windows. The key trick is that with all-positive values, a sliding window whose product stays under k can never help by shrinking further — so once a window [left, right] qualifies, every one of its right - left + 1 suffixes ending at right qualifies too, and they can all be counted in a single step.

Test Case 1:

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

Output:8

Explanation:The 8 qualifying subarrays are [10], [5], [2], [6], [10,5], [5,2], [2,6], and [5,2,6].

Test Case 2:

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

Output:0

Explanation:No product of positive integers can ever be less than 0.

Test Case 3:

Input:nums = [1, 1, 1], k = 2

Output:6

Explanation:Every one of the 6 subarrays has product 1, which is less than 2.

Constraints

◆1 ≤ nums.length ≤ 3 × 10⁴
◆1 ≤ nums[i] ≤ 1000
◆0 ≤ k ≤ 10⁶

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

nums (comma-separated) — 2-8 positive integers (1-20)k — 0 or greater

1	class Solution {
2	public int countSubarraysWithProductLessThanK(int[] nums, int k) {
3	if (k <= 1) return 0;
4	int left = 0, product = 1, count = 0;
5	for (int right = 0; right < nums.length; right++) {
6	product *= nums[right];
7	while (product >= k) {
8	product /= nums[left];
9	left++;
10	}
11	count += right - left + 1;
12	}
13	return count;
14	}
15	}
16

↑left

Variables

left0

product1

count0

INITIALIZE

Start left at 0, product at 1, and count at 0. Grow the window to the right, keeping product below k = 100.

Step 1 / 11

Approach & Solutions

Brute Force

Brute

For every starting index, extend a running product one element at a time and count the subarray as soon as the product stays under k. Stop extending as soon as the product reaches k, since every value is positive and the product can only grow from there. Correct, but every window shares almost all of its work with the one before it.

TimeO(n²)

SpaceO(1)

Java

Try it out

class Solution {
    public int countSubarraysWithProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            int product = 1;
            for (int j = i; j < nums.length; j++) {
                product *= nums[j];
                if (product >= k) break;
                count++;
            }
        }
        return count;
    }
}

Optimal — Sliding Window

Optimal

Grow a window [left, right] by multiplying in nums[right]. Whenever the product reaches k, divide out nums[left] and shrink the window from the left until it's under k again. Every subarray ending at right and starting anywhere from left to right also has product less than k — since dropping leading elements can only shrink the product — so all right - left + 1 of them are counted at once, without re-checking each one.

TimeO(n)