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.
Example 1:
Input: nums = [10,5,2,6], k = 100 Output: 8 Explanation: The 8 subarrays that have product less than 100 are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6] Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.
Example 2:
Input: nums = [1,2,3], k = 0 Output: 0
Constraints:
1 <= nums.length <= 3 * 1041 <= nums[i] <= 10000 <= k <= 106Problem Overview: Given an integer array nums and an integer k, count the number of contiguous subarrays whose product is strictly less than k. The challenge is avoiding the obvious quadratic enumeration while maintaining the product constraint efficiently.
Approach 1: Brute Force (O(n²) time, O(1) space)
The straightforward method enumerates every possible subarray starting at index i. For each start position, keep a running product while extending the subarray to the right. Each time the product remains less than k, increment the count. Once the product becomes greater than or equal to k, further expansion from that start index will only increase the product, so you can stop early for that starting point. This approach is easy to reason about and demonstrates understanding of contiguous subarray enumeration in an array. However, the worst‑case runtime still reaches O(n²), which becomes slow for large inputs.
Approach 2: Sliding Window / Two Pointers (O(n) time, O(1) space)
The optimal solution uses the sliding window technique. Maintain two pointers left and right that define a window and track the running product of elements inside it. Expand the window by moving right and multiplying the new value into the product. If the product becomes greater than or equal to k, shrink the window by moving left forward and dividing its value from the product until the constraint is satisfied again.
The key observation: when the product of the current window is less than k, every subarray ending at right and starting anywhere between left and right is valid. That means you can add right - left + 1 to the answer in constant time instead of enumerating each subarray individually. Each element enters and leaves the window at most once, giving a linear O(n) runtime.
This works because all numbers are positive, so expanding the window always increases the product and shrinking always decreases it. If negative or zero values were allowed, the monotonic behavior would break and a different strategy such as prefix techniques or specialized prefix sum transformations would be required.
Recommended for interviews: Interviewers expect the sliding window approach. Starting with brute force shows you understand the problem and the contiguous constraint. Transitioning to the two‑pointer optimization demonstrates pattern recognition and the ability to reduce quadratic scans to linear time.
The sliding window approach allows us to efficiently find subarrays where the product is less than k. By maintaining a window (two pointers), we can dynamically adjust the size of the current subarray based on the product of its elements. As the window size grows, the product is updated; if it exceeds k, we reduce the window from the left until the product is again less than k. This method minimizes redundant calculations.
The solution leverages a sliding window (or two-pointer) technique. The product of elements within the window is maintained, and pointers left and right are used to denote the current subarray. If the product exceeds k, the left pointer is moved to shrink the window until the product is less than k. The count of subarrays ending at each index is added to the total count.
Time Complexity: O(n) - Each element is processed at most twice.
Space Complexity: O(1) - Only a constant amount of extra space is used.
The brute force approach involves checking every possible subarray within nums and calculating their products. Each subarray is counted if its product is less than k. Though less efficient, it guarantees correctness by examining all potential subarrays.
This C function explores all subarrays starting from each index and computes their products. It stops extending a subarray when its product reaches or exceeds k, thereby optimizing to some degree compared to recalculating products from scratch for each subarray.
Time Complexity: O(n^2) - Considers all possible subarrays.
Space Complexity: O(1) - Constant extra space used.
We can use two pointers to maintain a sliding window, where the product of all elements in the window is less than k.
Define two pointers l and r pointing to the left and right boundaries of the sliding window, initially l = r = 0. We use a variable p to record the product of all elements in the window, initially p = 1.
Each time, we move r one step to the right, adding the element x pointed to by r to the window, and update p = p times x. Then, if p geq k, we move l one step to the right in a loop and update p = p \div nums[l] until p < k or l \gt r. Thus, the number of contiguous subarrays ending at r with a product less than k is r - l + 1. We then add this number to the answer and continue moving r until r reaches the end of the array.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Kotlin
C#
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: |
| Brute Force Approach | Time Complexity: |
| Two Pointers | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n²) | O(1) | Useful for understanding the problem or when constraints are small |
| Sliding Window (Two Pointers) | O(n) | O(1) | Optimal solution for positive integers; standard interview approach |
LeetCode 713. Subarray Product Less Than K (Algorithm Explained) • Nick White • 37,248 views views
Watch 9 more video solutions →Practice Subarray Product Less Than K with our built-in code editor and test cases.
Practice on FleetCode