Subarray Product Less Than K

Master this topic with zero to advance depth.

Subarray Product Less Than K

Count the number of contiguous subarrays where the product of all elements is strictly less than k.

Visual Representation

nums = [10, 5, 2, 6], k = 100

[10] -> Prod: 10 (<100) Count +1
[10, 5] -> Prod: 50 (<100) Count +2 (new: [5], [10,5])
[10, 5, 2] -> Prod: 100 (>=100) -> Shrink left
[5, 2] -> Prod: 10 (<100) Count +2 (new: [2], [5,2])

Rule: Subarrays ending at 'right' = right - left + 1

Medium

Examples

Input: nums = [10,5,2,6], k = 100
Output: 8

Approach 1

Level I: Brute Force

Intuition

Iterate through every possible starting point i and ending point j. For each pair, calculate the product of elements in nums[i...j]. If the product is less than k, increment the count.

Thought Process

Outer loop i from 0 to n-1.
Inner loop j from i to n-1.
Calculate prod = prod * nums[j].
If prod < k, count++.
If prod >= k, break inner loop (since elements are positive, product will only increase).

⏱ O(N^2)💾 O(1)

Detailed Dry Run

i	j	Prod	Result
0	0 (10)	10	Count 1
0	1 (5)	50	Count 2
0	2 (2)	100	STOP
1	1 (5)	5	Count 3

java

public class Main {
    public static int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            long prod = 1;
            for (int j = i; j < nums.length; j++) {
                prod *= nums[j];
                if (prod < k) count++;
                else break;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(numSubarrayProductLessThanK(new int[]{10, 5, 2, 6}, 100)); // 8
    }
}

Approach 2

Level II: Log-Sum Prefix Sums + Binary Search (O(N log N))

Intuition

We can transform the product comparison into a sum comparison using logarithms: $\prod x_i < K \iff \sum \log(x_i) < \log(K)$ . Since all elements are positive, the prefix sums of $\log(x_i)$ are monotonically increasing, allowing us to use Binary Search for each starting point.

Thought Process

Precompute an array prefixLogs where prefixLogs[i] is the sum of log(nums[0...i-1]).
For each starting index i, we need to find the largest j such that prefixLogs[j+1] - prefixLogs[i] < log(K) - epsilon (to handle floating point precision).
The number of such j's for a fixed i is j - i + 1.

Pattern: Logarithmic Transformation

⏱ O(N log N) - For each of the $N$ starting points, we perform a binary search.💾 O(N) to store the prefix logs.

java

public class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;
        int n = nums.length;
        double[] prefixLogs = new double[n + 1];
        for (int i = 0; i < n; i++) {
            prefixLogs[i + 1] = prefixLogs[i] + Math.log(nums[i]);
        }

        double logK = Math.log(k);
        int count = 0;
        for (int i = 0; i < n; i++) {
            int low = i + 1, high = n, ans = i;
            while (low <= high) {
                int mid = low + (high - low) / 2;
                if (prefixLogs[mid] - prefixLogs[i] < logK - 1e-9) {
                    ans = mid;
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
            count += (ans - i);
        }
        return count;
    }
}

Approach 3

Level III: Optimal (Sliding Window)

Intuition

Thought Process

Standard variable-size sliding window. The key observation is that if a window [left, right] has a product < k, then ALL subarrays ending at right and starting between left and right also have products < k. There are right - left + 1 such subarrays.

Patterns

Window-based Counting: Add Right - Left + 1 to result.
Product Control: Divide by nums[left] when product $\ge k$ .

⏱ O(N)💾 O(1)

Detailed Dry Run

Right	Num	Product	Left	Count Add	Total
0	10	10	0	1	1
1	5	50	0	2	3
2	2	100->10	1	2	5
3	6	60	1	3	8

java

public class Main {
    public static int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;
        int prod = 1, res = 0, left = 0;
        for (int right = 0; right < nums.length; right++) {
            prod *= nums[right];
            while (prod >= k && left <= right) prod /= nums[left++];
            res += right - left + 1;
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(numSubarrayProductLessThanK(new int[]{10, 5, 2, 6}, 100));
    }
}

⚠️ Common Pitfalls & Tips

Edge case k <= 1 is critical because the product of any subarray of positive integers is at least 1, which wouldn't be strictly less than 1.

← Previous QuestionMaximum Number of Vowels in a Substring of Given Length

Next Question →Longest Turbulent Subarray

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.