Log inSign up
mediumLeetCodeNot Started

Subarray Product Less Than K

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

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.

A subarray is a contiguous sequence of elements within an array.

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 100, which is not strictly less than 100.

Example 2:

Input: nums = [1, 2, 3], k = 0
Output: 0
Explanation: Since all elements are positive integers (>= 1), no subarray product can be strictly less than 0.

Constraints:

  • 1 <= nums.length <= 3 * 104
  • 1 <= nums[i] <= 1000
  • 0 <= k <= 106

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Sliding Window Fundamentals (Two Pointers)
  • Subarray Counting Mechanics (Prefix/Suffix subsegments)
  • Monotonicity of Multiplicative Window on Positive Numbers

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the counting principle: a valid window [left, right] contributes exactly (right - left + 1) subarrays ending at right.
  • Handle multiplicative edge cases: understand why k <= 1 yields 0 for positive integer arrays.
  • Understand window monotonicity: why strictly positive numbers guarantee monotonic expansion/shrinkage.
  • Implement clean division-based window shrinkage without division-by-zero risk.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Problem asks to count contiguous subarrays satisfying a product threshold constraint.
  • All elements are strictly positive integers (monotone product growth when expanding, monotone reduction when shrinking).
  • Strict condition < k where k can be 0 or 1.

Algorithmic Decision Tree:

  • If k <= 1, return 0 immediately (since nums[i] >= 1, min product is 1 >= k).
  • Maintain running product prod = 1, left = 0. For each right from 0 to n - 1, do prod *= nums[right].
  • While prod >= k and left <= right, divide prod /= nums[left++].
  • Add (right - left + 1) to the global answer count.

Connected Patterns:

Subarray Sum Equals K (Prefix Sums + Hash Map, used when numbers can be negative)Fruit Into Baskets (Dynamic sliding window tracking distinct counts)Subarrays with K Different Integers (AtMost(K) - AtMost(K-1) counting paradigm)

1. Brute Force (Nested Loops)

Intuition

Check every possible subarray by fixing the start index i and multiplying elements until the product reaches or exceeds k.

Algorithm

  1. If k <= 1, return 0.
  2. Initialize count = 0.
  3. Loop i from 0 to nums.length - 1:
  4. Set prod = 1.
  5. Loop j from i to nums.length - 1:
  6. prod *= nums[j]
  7. If prod < k, increment count.
  8. Else, break early because all elements are positive (product will only grow).
  9. Return count.

All Subarrays Product (O(N^2) Time)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Single element [10] qualifies
Visual state
Values and pointers at this exact step
pointers
S
10
5
2
6
0
↑ i=j
1
2
3
Variables at this step
i
0
j
0
product
10
count
1
Check / comparison
Range [0..0]: product = 10 < 100
Decision / next transition
Valid! count = 1.
Why this step matters

Single element [10] qualifies.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 int numSubarrayProductLessThanK(std::vector<int>& nums, int k) {
7 if (k <= 1) return 0;
8 int n = nums.size();
9 int count = 0;
10 for (int i = 0; i < n; ++i) {
11 long long prod = 1;
12 for (int j = i; j < n; ++j) {
13 prod *= nums[j];
14 if (prod < k) {
15 count++;
16 } else {
17 break;
18 }
19 }
20 }
21 return count;
22 }
23};
24
25int main() {
26 Solution sol;
27 std::vector<int> nums = {10, 5, 2, 6};
28 int k = 100;
29 std::cout << sol.numSubarrayProductLessThanK(nums, k) << std::endl; // Output: 8
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(N^2) — Time complexity for Brute Force (Nested Loops).
  • Space complexity: O(1) — Space complexity for Brute Force (Nested Loops).

Why Brute Force Doesn't Scale:

For N = 30,000, N2 / 2 is ~450 million operations, triggering Time Limit Exceeded (TLE).

With N = 30,000, the O(N) sliding window executes in under 5ms using only 2 pointers and a running product accumulator.

2. Prefix Logarithms + Binary Search

Intuition

Convert product to sum by taking logarithms: log(a * b) = log(a) + log(b). The condition prod(nums[i..j]) < k becomes prefixLog[j+1] - prefixLog[i] < log(k) - 1e-9. For each i, binary search the furthest j.

Algorithm

  1. If k <= 1, return 0.
  2. Build a prefix sum array of logarithms: prefixLogs[x] = sum(log(nums[0..x-1])).
  3. Target log limit is log(k) - 1e-9 (to strictly satisfy < k).
  4. For each index i, binary search the upper bound index j where prefixLogs[j+1] - prefixLogs[i] < log(k) - 1e-9.
  5. Add (j - i + 1) to count.
  6. Return total count.

Prefix Logarithms + Binary Search (O(N log N) Time)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Logarithms convert multiplication into addition, making prefix sums strictly monotonic
Visual state
Values and pointers at this exact step
pointers
S
10
5
2
6
0
↑ log
1
2
3
Variables at this step
targetLog
4.605
count
0
Check / comparison
Compute log array and prefix sums: targetLog = log(100) = 4.605
Decision / next transition
Product < k is mathematically equivalent to prefixLog[j] - prefixLog[i] < log(k).
Why this step matters

Logarithms convert multiplication into addition, making prefix sums strictly monotonic.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <cmath>
4#include <algorithm>
5
6class Solution {
7public:
8 int numSubarrayProductLessThanK(std::vector<int>& nums, int k) {
9 if (k <= 1) return 0;
10 int n = nums.size();
11 std::vector<double> prefix(n + 1, 0.0);
12 for (int i = 0; i < n; ++i) {
13 prefix[i + 1] = prefix[i] + std::log(nums[i]);
14 }
15
16 double logK = std::log(k);
17 int count = 0;
18 for (int i = 0; i < n; ++i) {
19 // Find max index j such that prefix[j+1] - prefix[i] < logK - 1e-9
20 double target = prefix[i] + logK - 1e-9;
21 auto it = std::lower_bound(prefix.begin() + i + 1, prefix.end(), target);
22 int j = std::distance(prefix.begin(), it) - 1;
23 count += (j - i);
24 }
25 return count;
26 }
27};
28
29int main() {
30 Solution sol;
31 std::vector<int> nums = {10, 5, 2, 6};
32 int k = 100;
33 std::cout << sol.numSubarrayProductLessThanK(nums, k) << std::endl; // Output: 8
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(N log N) — Time complexity for Prefix Logarithms + Binary Search.
  • Space complexity: O(N) — Space complexity for Prefix Logarithms + Binary Search.

3. Dynamic Sliding Window (Two Pointers)

Intuition

Maintain a window [left, right] where the product of all elements is strictly less than k. For each right, multiply prod *= nums[right]. If prod >= k, shrink left by prod /= nums[left++]. The window [left, right] introduces exactly right - left + 1 new valid subarrays ending at index right.

Algorithm

  1. If k <= 1, return 0 immediately because all nums[i] >= 1.
  2. Initialize prod = 1, left = 0, totalCount = 0.
  3. Iterate right from 0 to nums.length - 1:
  4. Multiply prod *= nums[right].
  5. While prod >= k and left <= right:
  6. Divide prod /= nums[left] and increment left.
  7. Add (right - left + 1) to totalCount.
  8. Return totalCount.

Sliding Window Suffix Counting (O(N) Time, O(1) Space)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Every valid window [L
Visual state
Values and pointers at this exact step
pointers
S
10
5
2
6
0
↑ L=R
1
2
3
Variables at this step
L
0
R
0
prod
10
added
1
count
1
Check / comparison
R = 0, multiply nums[0] (10): prod = 10 < 100
Decision / next transition
Valid window [0..0]. Add R - L + 1 = 1 subarray ([10]). count = 1.
Why this step matters

Every valid window [L..R] introduces exactly (R - L + 1) new subarrays ending at R.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 int numSubarrayProductLessThanK(std::vector<int>& nums, int k) {
7 // Base edge case: since nums[i] >= 1, product is at least 1.
8 // If k <= 1, no product can be strictly less than k.
9 if (k <= 1) return 0;
10
11 int n = nums.size();
12 long long prod = 1;
13 int left = 0;
14 int count = 0;
15
16 for (int right = 0; right < n; ++right) {
17 prod *= nums[right];
18
19 // Shrink window from the left until product is strictly less than k
20 while (prod >= k && left <= right) {
21 prod /= nums[left];
22 left++;
23 }
24
25 // Subarrays ending at __SF_TOKEN_A__: nums[right], nums[right-1..right], ..., nums[left..right]
26 count += (right - left + 1);
27 }
28
29 return count;
30 }
31};
32
33int main() {
34 Solution sol;
35 std::vector<int> nums = {10, 5, 2, 6};
36 int k = 100;
37 std::cout << sol.numSubarrayProductLessThanK(nums, k) << std::endl; // Output: 8
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(N) — Time complexity for Dynamic Sliding Window (Two Pointers).
  • Space complexity: O(1) — Space complexity for Dynamic Sliding Window (Two Pointers).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force (Nested Loops)O(N^2)O(1)Iterate over all possible starting indices i and calculate running product until it reaches >= k or ends.Redundantly re-multiplies overlapping subarray segments from scratch.
2.Log-Transformed Prefix Sums + Binary SearchO(N log N)O(N)Transform prod < k to sum(log(nums[i])) < log(k). Build prefix sums of log values and binary search for each starting index.Binary search over float logs has overhead and precision issues.
3.Sliding Window (Two Pointers)OptimalO(N)O(1)Expand right, shrink left when prod >= k. Add (right - left + 1) at each step.None. Single pass over the array.

Common Pitfalls & Crucial Edge Cases

Missing the `k <= 1` Edge Case

Without this guard, if nums = [1, 2, 3], k = 0, prod >= k remains true even when left > right, causing out-of-bounds array access or infinite looping.

Counting Window Combinations Incorrectly

Adding windowSize * (windowSize + 1) / 2 at every step results in massive duplicate counting. Instead, only add (right - left + 1) which counts subarrays ending *strictly* at right.

Using Float Division in Integer Languages

Using / in Python 3 produces floats which can lose precision. Use //= in Python.

Attempting Prefix Products with Modulo

Subarray product cannot use prefix products modulo arithmetic because the condition is a strict magnitude inequality < k, not an equality.

Crucial Edge Cases to Validate:

  • k <= 1 — Since all elements are positive integers (nums[i] >= 1), the minimum possible subarray product is 1. If k = 0 or k = 1, no subarray can have a product < k. Handled immediately with an early exit guard if (k <= 1) return 0;.
  • Single Element Arrays — e.g., nums = [5], k = 5 returns 0; nums = [5], k = 10 returns 1.
  • All Elements Greater Than k — e.g., nums = [10, 20, 30], k = 5. Window shrinks repeatedly with left > right, contributing 0 at each step.
  • All Elements Less Than k — e.g., nums = [1, 1, 1], k = 2. Window continuously expands to full length, returning N * (N + 1) / 2.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the edge case k <= 1 right after reading the constraints: interviewers look for this immediate insight.
  2. Clearly explain the right - left + 1 formula: illustrate it with a small concrete example like [5, 2] ending at 2 producing [2] and [5, 2].
  3. Explain why monotonicity holds: mention explicitly that nums[i] >= 1 is what enables the two-pointer sliding window approach.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does adding (right - left + 1) avoid duplicate counts across iterations?

2.Why must we return 0 immediately if k <= 1 when nums[i] >= 1?

3.What would happen if the array contained negative numbers or zeros?

Back to DSA Sheet