Subarray Product Less Than K
Understanding the Problem
We need to count every contiguous subarray whose product stays strictly below k. A subarray is a contiguous slice of the original array, so [5, 2] counts but [10, 2] (skipping 5) does not.
All elements are positive integers (at least 1), so extending a subarray to the right can only keep the product the same or increase it. It never decreases. This monotonic behavior points toward a sliding window: once a window's product reaches the threshold, shrinking it from the left brings the product back down.
One edge case to handle up front. If k <= 1, no subarray can have a product below k, since all elements are at least 1, so the answer is 0.
Key Constraints:
1 <= nums.length <= 3 * 10^4→ With n up to 30,000, an O(n^2) scan is about 450 million subarray checks, slow enough to risk a time limit. The target is O(n).1 <= nums[i] <= 1000→ All positive, so the product is non-decreasing as we extend a subarray. This is what makes the sliding window valid.0 <= k <= 10^6→ A running product that stays belowknever exceeds aboutk * 1000 = 10^9, which fits in a signed 32-bit integer. Multiplying one more element past that point can overflow, so the loop must stop counting once the product reachesk.
Approach 1: Brute Force
Intuition
Check every possible subarray, compute its product, and count the ones whose product is below k. Fix a starting index, extend to the right multiplying as we go, and stop once the product reaches k. Because all elements are positive, the product only grows from there, so any longer subarray with the same start is also invalid.
Algorithm
- Initialize a counter to 0.
- For each starting index
ifrom 0 to n-1: - Set
product = 1. - For each ending index
jfromito n-1: - Multiply
productbynums[j]. - If
product < k, increment the counter. - Otherwise, break out of the inner loop (product can only grow from here).
- Return the counter.
Visualization and Code
Loading animation...
- Time Complexity: O(n^2). For each of the n starting positions, we may extend up to n elements in the worst case. The early break helps when k is small, but in the worst case (k very large), every subarray is valid and we check all n*(n+1)/2 of them.
- Space Complexity: O(1). We only use a few variables regardless of input size.
The brute force re-scans forward from every starting index, discarding work from the previous start. The monotonic product lets us replace those repeated scans with a single window that grows and shrinks in one pass.
Approach 2: Sliding Window
Intuition
Because every element is at least 1, extending a window to the right can only increase or maintain the product, and shrinking from the left can only decrease or maintain it. This monotonic property is what makes a sliding window work.
We maintain a window [left, right] and track the running product. As we expand right, we multiply the new element into the product. If the product reaches k, we shrink from the left by dividing out nums[left] and advancing left. After adjusting, every subarray that ends at right and starts at any index from left to right has a product below k, which is right - left + 1 new subarrays.
The count right - left + 1 comes from listing the subarrays that end at index right within the current window: [left..right], [left+1..right], ..., [right..right]. Each one drops elements from the left of the window, so its product is at most the window product, which is already below k. All of them are valid, and we count them in O(1) instead of one at a time.
Summing right - left + 1 over every right counts each valid subarray once and never twice. Every subarray has exactly one rightmost index, so it is counted only when right reaches that index, never before and never after. No subarray is missed either, because when right reaches its last element, left has already shrunk to the smallest start whose product is below k, so every valid start for that ending is included in the range.
Algorithm
- If
k <= 1, return 0 (no valid subarrays possible since all products are at least 1). - Initialize
left = 0,product = 1, andcount = 0. - For each
rightfrom 0 to n-1: - Multiply
productbynums[right]. - While
product >= k, divideproductbynums[left]and incrementleft. - Add
right - left + 1tocount. - Return
count.
Visualization and Code
Loading animation...
- Time Complexity: O(n). The
rightpointer moves from 0 to n-1, visiting each element once. Theleftpointer also moves from 0 to at most n-1 across the entire execution. Even though there's a while loop inside the for loop,leftnever moves backward, so the total number of iterations across all while loops is at most n. - Space Complexity: O(1). We only use a fixed number of variables:
count,product,left, andright.