Watch 10 video solutions for Subarray Product Less Than K, a medium level problem involving Array, Binary Search, Sliding Window. This walkthrough by Nick White has 37,248 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |