Subarray Product Less Than K

Medium
244.

Subarray Product Less Than K

Subarray Product Less Than K is a medium coding problem on arrays, binary search and prefix sum, asked in Amazon, Google and Meta interviews.

Given an array of positive integers nums and an integer k, return the number of contiguous subarrays whose product is strictly less than k.

Example 1

Input
nums = [10,5,2,6], k = 100
Output
8
Explanation
The eight are [10], [5], [2], [6], [10,5], [5,2], [2,6] and [5,2,6].

Example 2

Input
nums = [1,2,3], k = 0
Output
0
Explanation
No product is below 0.

Example 3

Input
nums = [1,1,1], k = 2
Output
6

Constraints

  • 1 <= nums.length <= 30
  • 1 <= nums[i] <= 20
  • 0 <= k <= 1000000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var numSubarrayProductLessThanK = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Subarray Product Less Than K — Problem & Solution

Subarray Product Less Than K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Subarray Product Less Than K is a medium coding problem on arrays, binary search and prefix sum, asked in Amazon, Google and Meta interviews.

Problem statement

Given an array of positive integers nums and an integer k, return the number of contiguous subarrays whose product is strictly less than k.

Example 1

Input: nums = [10,5,2,6], k = 100
Output: 8
Explanation: The eight are [10], [5], [2], [6], [10,5], [5,2], [2,6] and [5,2,6].

Example 2

Input: nums = [1,2,3], k = 0
Output: 0
Explanation: No product is below 0.

Example 3

Input: nums = [1,1,1], k = 2
Output: 6

Constraints

  • 1 <= nums.length <= 30
  • 1 <= nums[i] <= 20
  • 0 <= k <= 1000000

Hints for Subarray Product Less Than K

  1. Hint 1

    All values are positive, so growing the window can only increase the product — the window is monotone.

  2. Hint 2

    Expand right, then shrink from the left while the product is at least k.

  3. Hint 3

    A window [left, right] contributes right - left + 1 subarrays: every one that ends at right.

How to solve Subarray Product Less Than K

All values are positive, so a window's product only grows as it widens. Expand the right end, shrink from the left while the product is at least k, and count right - left + 1 subarrays ending at right.

Approach

  1. Return 0 if k <= 1 — no product of positive integers is below 1.
  2. For each right, multiply product by nums[right].
  3. While product >= k, divide out nums[left] and advance left.
  4. Add right - left + 1 to the count.

Why it works

Once the window [left, right] has product below k, every suffix of it — the subarrays ending at right — also does, and there are right - left + 1 of them. Monotonicity guarantees the left pointer never needs to move backwards.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Without the k <= 1 guard, the shrink loop can run past right when a single element already fails.
  • The comparison is strict — product < k.

Reference solution

Python

def numSubarrayProductLessThanK(nums, k: int) -> int:
    if k <= 1:
        return 0
    product, left, count = 1, 0, 0
    for right, x in enumerate(nums):
        product *= x
        while product >= k:
            product //= nums[left]
            left += 1
        count += right - left + 1
    return count

Java

public static int numSubarrayProductLessThanK(int[] nums, int k) {
    if (k <= 1) return 0;
    long product = 1;
    int left = 0, count = 0;
    for (int right = 0; right < nums.length; right++) {
        product *= nums[right];
        while (product >= k) {
            product /= nums[left];
            left++;
        }
        count += right - left + 1;
    }
    return count;
}

C++

int numSubarrayProductLessThanK(vector<int>& nums, int k) {
    if (k <= 1) return 0;
    long long product = 1;
    int left = 0, count = 0;
    for (int right = 0; right < (int) nums.size(); right++) {
        product *= nums[right];
        while (product >= k) {
            product /= nums[left];
            left++;
        }
        count += right - left + 1;
    }
    return count;
}

JavaScript

var numSubarrayProductLessThanK = function(nums, k) {
    if (k <= 1) return 0;
    let product = 1, left = 0, count = 0;
    for (let right = 0; right < nums.length; right++) {
        product *= nums[right];
        while (product >= k) {
            product /= nums[left];
            left++;
        }
        count += right - left + 1;
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search