AlgoInsight

DSA problem

Subarray Product Less Than K

MediumSliding Window - Dynamic SizePattern: Variable-Size Sliding Windowtop600AmazonGoogleMicrosoftBloomberg

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

Because every element is a positive integer, the product of a window is a monotonic quantity: extending the window can only increase the product, and shrinking it can only decrease it. This monotonicity is exactly what makes a variable-size sliding window applicable.

The strategy is to maintain a window whose running product stays below k. As you advance the right pointer, multiply its value into the running product. If the product reaches or exceeds k, advance the left pointer and divide out its values until the product drops back below k. For each valid right position, every subarray that ends at right and starts anywhere within the current window is valid, so the window's width (right - left + 1) is the count of new subarrays to add.

Examples

Example 1
Input: nums = [10,5,2,6], k = 100
Output: 8
Explanation: The 8 subarrays with product less than 100 are: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]. The subarray [10,5,2] has product 100, which is not strictly less than 100.
Example 2
Input: nums = [1,2,3], k = 0
Output: 0
Explanation: No subarray can have a product strictly less than 0 because all elements are positive, so every product is at least 1.
Example 3
Input: nums = [1,1,1], k = 2
Output: 6
Explanation: Every contiguous subarray has product 1, which is less than 2. There are 6 such subarrays: three of length 1, two of length 2, and one of length 3.

Constraints

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

sliding-windowarraytwo-pointers

Browse all DSA problems