Subarray Product Less Than K - Solution & Explanation
Problem Statement
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 <= 106
Approach Overview
Problem 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 1: Sliding Window Approach
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.
Complexity
Time Complexity: O(n) - Each element is processed at most twice.
Space Complexity: O(1) - Only a constant amount of extra space is used.
Approach 2: Brute Force Approach
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.
Complexity
Time Complexity: O(n^2) - Considers all possible subarrays.
Space Complexity: O(1) - Constant extra space used.
Approach 3: Two Pointers
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).
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Kotlin
C#
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: |
| Brute Force Approach | Time Complexity: |
| Two Pointers | — |
Detailed Complexity Analysis
| 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 |
Video Solution
LeetCode 713. Subarray Product Less Than K (Algorithm Explained) • Nick White • 37,378 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Subarray Product Less Than K easy or hard?
Subarray Product Less Than K Python/Java solution
How to solve Subarray Product Less Than K in O(n)?
What is the best approach for Subarray Product Less Than K?
Is Subarray Product Less Than K asked at Google/Amazon/Meta?
What data structure is used in Subarray Product Less Than K?
What is the time complexity of Subarray Product Less Than K?
Ready to solve this problem?
Practice Subarray Product Less Than K with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor