Subarray Product Less Than K solution and explanation
Google
TCS
9 more videos on this problem
LeetCode 713. Subarray Product Less Than K (Algorithm Explained)Nick White · 9:54 · 37K views
Subarray Product Less Than K - Leetcode 713 - PythonNeetCodeIO · 10:26 · 30K views
Subarray Product Less Than K | Khandani Sliding Window template | Leetcode 713 | codestorywithMIKcodestorywithMIK · 16:55 · 22K views
713. Subarray Product Less Than K | 2 Pointers | Binary Search | 4 ApproachesAryan Mittal · 15:40 · 8K views
Subarray Product Less Than K | Brute Force to Optimised (Sliding Window) | O(N) Approach ExplainedRisingBrain · 21:13 · 8K views
Subarray Product Less Than K | Leet code 713 | Theory explained + Python codeSai Anish Malla · 10:24 · 5K views
LeetCode 713 | Subarray Product Less Than K | Solution Explained (Java + Whiteboard)Xavier Elon · 9:51 · 3K views
Daily LeetCode Challenge: 713. Subarray Product Less Than K | C++ | Sliding Window | 2-PointersSHWETA BHAGAT · 12:42 · 546 views
Subarray Product Less Than K - Leetcode 713Lit Code · 9:24 · 405 views
Subarray Product Less Than K | LeetCode 713 | September LeetCode Challenge | Day 28Learn Code Repeat · 14:37 · 246 views
The problem
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.
def numSubarrayProductLessThanK(nums, k):
if k <= 1: return 0
prod = 1
count = left = 0
for right, val in enumerate(nums):
prod *= val
while prod >= k:
prod /= nums[left]
left += 1
count += right - left + 1
return countpublic class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
if (k <= 1) return 0;
int prod = 1, count = 0, left = 0;
for (int right = 0; right < nums.length; right++) {
prod *= nums[right];
while (prod >= k) prod /= nums[left++];
count += right - left + 1;
}
return count;
}
}#include <vector>
using namespace std;
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
if (k <= 1) return 0;
int prod = 1, count = 0, left = 0;
for (int right = 0; right < nums.size(); right++) {
prod *= nums[right];
while (prod >= k) prod /= nums[left++];
count += right - left + 1;
}
return count;
}var numSubarrayProductLessThanK = function(nums, k) {
if (k <= 1) return 0;
let prod = 1, count = 0, left = 0;
for (let right = 0; right < nums.length; right++) {
prod *= nums[right];
while (prod >= k) prod /= nums[left++];
count += right - left + 1;
}
return count;
};#include <stdio.h>
int numSubarrayProductLessThanK(int* nums, int numsSize, int k) {
if (k <= 1) return 0;
int prod = 1, count = 0, left = 0;
for (int right = 0; right < numsSize; right++) {
prod *= nums[right];
while (prod >= k) prod /= nums[left++];
count += right - left + 1;
}
return count;
}public class Solution {
public int NumSubarrayProductLessThanK(int[] nums, int k) {
if (k <= 1) return 0;
int prod = 1, count = 0, left = 0;
for (int right = 0; right < nums.Length; right++) {
prod *= nums[right];
while (prod >= k) prod /= nums[left++];
count += right - left + 1;
}
return count;
}
}This Python function implements the same sliding window algorithm. The product is maintained and adjusted based on the current subarray defined by the left and right pointers. The count of qualifying subarrays is incremented for each valid window.
Time Complexity: O(n)
Space Complexity: O(1)
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.
def numSubarrayProductLessThanK_bruteforce(nums, k):
if k <= 1: return 0
count = 0
for start in range(len(nums)):
prod = 1
for end in range(start, len(nums)):
prod *= nums[end]
if prod >= k:
break
count += 1
return countpublic class Solution {
public int numSubarrayProductLessThanK_bruteforce(int[] nums, int k) {
if (k <= 1) return 0;
int count = 0;
for (int start = 0; start < nums.length; start++) {
int prod = 1;
for (int end = start; end < nums.length; end++) {
prod *= nums[end];
if (prod >= k) break;
count++;
}
}
return count;
}
}#include <vector>
using namespace std;
int numSubarrayProductLessThanK_bruteforce(vector<int>& nums, int k) {
if (k <= 1) return 0;
int count = 0;
for (int start = 0; start < nums.size(); start++) {
int prod = 1;
for (int end = start; end < nums.size(); end++) {
prod *= nums[end];
if (prod >= k) break;
count++;
}
}
return count;
}var numSubarrayProductLessThanK_bruteforce = function(nums, k) {
if (k <= 1) return 0;
let count = 0;
for (let start = 0; start < nums.length; start++) {
let prod = 1;
for (let end = start; end < nums.length; end++) {
prod *= nums[end];
if (prod >= k) break;
count++;
}
}
return count;
};#include <stdio.h>
int numSubarrayProductLessThanK_bruteforce(int* nums, int numsSize, int k) {
if (k <= 1) return 0;
int count = 0;
for (int start = 0; start < numsSize; start++) {
int prod = 1;
for (int end = start; end < numsSize; end++) {
prod *= nums[end];
if (prod >= k) break;
count++;
}
}
return count;
}public class Solution {
public int NumSubarrayProductLessThanK_bruteforce(int[] nums, int k) {
if (k <= 1) return 0;
int count = 0;
for (int start = 0; start < nums.Length; start++) {
int prod = 1;
for (int end = start; end < nums.Length; end++) {
prod *= nums[end];
if (prod >= k) break;
count++;
}
}
return count;
}
}This Python function iterates through each start position and expands the subarray to examine all subarray products. If a product reaches k, it breaks out of the loop to improve efficiency.
Time Complexity: O(n^2)
Space Complexity: O(1)
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).
function numSubarrayProductLessThanK(nums: number[], k: number): number {
const n = nums.length;
let [ans, l, p] = [0, 0, 1];
for (let r = 0; r < n; ++r) {
p *= nums[r];
while (l <= r && p >= k) {
p /= nums[l++];
}
ans += r - l + 1;
}
return ans;
}func numSubarrayProductLessThanK(nums []int, k int) (ans int) {
l, p := 0, 1
for r, x := range nums {
p *= x
for l <= r && p >= k {
p /= nums[l]
l++
}
ans += r - l + 1
}
return
}class Solution {
fun numSubarrayProductLessThanK(nums: IntArray, k: Int): Int {
var ans = 0
var l = 0
var p = 1
for (r in nums.indices) {
p *= nums[r]
while (l <= r && p >= k) {
p /= nums[l]
l++
}
ans += r - l + 1
}
return ans
}
}impl Solution {
pub fn num_subarray_product_less_than_k(nums: Vec<i32>, k: i32) -> i32 {
let mut ans = 0;
let mut l = 0;
let mut p = 1;
for (r, &x) in nums.iter().enumerate() {
p *= x;
while l <= r && p >= k {
p /= nums[l];
l += 1;
}
ans += (r - l + 1) as i32;
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: |
| Brute Force Approach | Time Complexity: |
| Two Pointers | – |
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 |
Frequently asked questions
Is Subarray Product Less Than K easy or hard?
Subarray Product Less Than K is classified as a Medium problem on LeetCode. The difficulty comes from recognizing that enumerating all subarrays is unnecessary and that a sliding window can count valid ranges in linear time.
Subarray Product Less Than K Python/Java solution
Most implementations use the same sliding window logic across languages. Maintain two pointers, update the product while expanding the window, shrink when the product exceeds the limit, and accumulate the count using right - left + 1. The algorithm works identically in Python, Java, C++, C#, and JavaScript.
How to solve Subarray Product Less Than K in O(n)?
Use a sliding window with two pointers. Expand the window by moving the right pointer and multiply the new value into the running product. If the product becomes >= k, move the left pointer forward and divide values until the product is valid again. Add right - left + 1 to the result at each step.
What is the best approach for Subarray Product Less Than K?
The sliding window (two pointers) approach is the best solution. Maintain a running product while expanding the right pointer and shrink the window when the product becomes >= k. Each step counts all valid subarrays ending at the current index, resulting in O(n) time and O(1) space.
Is Subarray Product Less Than K asked at Google/Amazon/Meta?
Subarray product and sliding window problems appear frequently in interviews at companies like Amazon, Google, and Meta. The question tests two‑pointer reasoning, window maintenance, and recognizing when a monotonic property allows linear scanning.
What data structure is used in Subarray Product Less Than K?
The problem primarily uses the sliding window technique on an array with two pointers and a running product variable. No additional data structures are required beyond constant extra space.
What is the time complexity of Subarray Product Less Than K?
The optimal sliding window solution runs in O(n) time because each element is added to and removed from the window at most once. The brute force approach takes O(n^2) time since it checks every possible subarray.