Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Subarray Product Less Than K

Try it yourself
MediumProblemExternal link

Description

You get an array of positive integers nums and an integer k.

Return the number of contiguous subarrays whose product is strictly less than k.

Examples

Example 1

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

Output: 8

Explanation: The 8 subarrays are [10], [5], [2], [6], [10, 5], [5, 2], [2, 6] and [5, 2, 6]. [10, 5, 2] isn't one: its product is 100, not less than 100.

Example 2

Input: nums = [1, 2, 3], k = 0

Output: 0

Explanation: Every product is at least 1, so none is less than 0.

Constraints

  • 1 ≤ nums.length ≤ 3 × 10^4
  • 1 ≤ nums[i] ≤ 1000
  • 0 ≤ k ≤ 10^6

Editorial

Brute Force

Intuition

Try every start i. Multiply the numbers from i to the right one at a time, and count each subarray while its product is below k.

Every number is at least 1, so a product never shrinks as the subarray grows. The first time it reaches k, every longer subarray from i reaches it too, so you can stop and try the next start.

Step-by-Step Explanation

Let's try every start in nums = [10, 5, 2, 6], k = 100:

  1. Start at 0 and multiply to the right. 2 subarrays from 0 stay below 100. The next product reaches 100, so stop, because longer ones from 0 only get bigger.
  2. Start at 1 and multiply to the right. 3 subarrays from 1 stay below 100.
  3. Start at 2 and multiply to the right. 2 subarrays from 2 stay below 100.
  4. Start at 3 and multiply to the right. 1 subarray from 3 stays below 100.

That's 8 subarrays.

Multiply Out From Every Start — Each step starts at one index and counts the subarrays from there whose product stays below k (green).

Algorithm

  1. Set count = 0.
  2. For each start i:
    • set product = 1;
    • for each j from i: multiply product by nums[j]; if it's at least k, stop; otherwise add 1 to count.
  3. Return count.

Code

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        int count = 0;
        for (int i = 0; i < (int)nums.size(); i++) {
            long long product = 1;
            for (int j = i; j < (int)nums.size(); j++) {
                product *= nums[j];
                if (product >= k) break;        // longer subarrays from i only get bigger
                count++;
            }
        }
        return count;
    }
};

class Solution:
    def numSubarrayProductLessThanK(self, nums: list[int], k: int) -> int:
        count = 0
        for i in range(len(nums)):
            product = 1
            for j in range(i, len(nums)):
                product *= nums[j]
                if product >= k:
                    break                       # longer subarrays from i only get bigger
                count += 1
        return count

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            long product = 1;
            for (int j = i; j < nums.length; j++) {
                product *= nums[j];
                if (product >= k) break;        // longer subarrays from i only get bigger
                count++;
            }
        }
        return count;
    }
}

var numSubarrayProductLessThanK = function(nums, k) {
    let count = 0;
    for (let i = 0; i < nums.length; i++) {
        let product = 1;
        for (let j = i; j < nums.length; j++) {
            product *= nums[j];
            if (product >= k) break;            // longer subarrays from i only get bigger
            count++;
        }
    }
    return count;
};

Complexity Analysis

Time Complexity: O(n²)

When the products stay small (all 1s, say), every start multiplies all the way to the end.

Space Complexity: O(1)

Why This Approach Is Not Efficient

With 3 × 10^4 numbers that are all 1 and k = 10^6, no product ever reaches k, so the inner loop never stops early: 450,015,000 multiplications.

And it redoes work. The start i + 1 multiplies out almost the same numbers as the start i. Turn it around and count by where each subarray ends instead: for each right end, the subarrays with a small product all start at or after some smallest start, and a sliding window can track that start as the right end moves.

Optimal Approach - Sliding Window

Intuition

Keep a window [left, right] whose product is below k. Move right one step and multiply its number in. While the product is k or more, divide out nums[left] and move left on.

Now every subarray that ends at right and starts at left or later sits inside the window, so its product is below k too, and every one that starts before left isn't. That's exactly right - left + 1 subarrays, so add that many. Each subarray has one right end, so each is counted once.

One case first: every number is at least 1, so no product is ever below 1. When k ≤ 1 the answer is 0, and returning early also keeps the shrink from running past right.

Step-by-Step Explanation

Let's slide over nums = [10, 5, 2, 6], k = 100:

  1. The product is 10, below 100. Every window ending at 0 and starting at 0 or later counts, so add 1, which makes 1.
  2. The product is 50, below 100. Every window ending at 1 and starting at 0 or later counts, so add 2, which makes 3.
  3. The product is 100, not below 100, so shrink and 10 leaves.
  4. The product is 10, below 100. Every window ending at 2 and starting at 1 or later counts, so add 2, which makes 5.
  5. The product is 60, below 100. Every window ending at 3 and starting at 1 or later counts, so add 3, which makes 8.

The answer is 8.

Count the Windows Ending at Each Right — The window is shaded. After any shrink (the amber number leaves), every subarray ending at right inside the window counts (green).

Algorithm

  1. If k ≤ 1, return 0.
  2. Set product = 1, left = 0, count = 0.
  3. For each right:
    • multiply product by nums[right];
    • while product ≥ k: divide it by nums[left] and add 1 to left;
    • add right - left + 1 to count.
  4. Return count.

Code

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if (k <= 1) return 0;                   // every number is at least 1, so no product is below 1
        long long product = 1;
        int left = 0, count = 0;
        for (int right = 0; right < (int)nums.size(); right++) {
            product *= nums[right];             // grow
            while (product >= k) {              // shrink until the product is below k
                product /= nums[left];
                left++;
            }
            count += right - left + 1;          // every window ending at right, starting at left or later
        }
        return count;
    }
};

class Solution:
    def numSubarrayProductLessThanK(self, nums: list[int], k: int) -> int:
        if k <= 1:
            return 0                            # every number is at least 1, so no product is below 1
        product = 1
        left = count = 0
        for right, x in enumerate(nums):
            product *= x                        # grow
            while product >= k:                 # shrink until the product is below k
                product //= nums[left]
                left += 1
            count += right - left + 1           # every window ending at right, starting at left or later
        return count

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;                   // every number is at least 1, so no product is below 1
        long product = 1;
        int left = 0, count = 0;
        for (int right = 0; right < nums.length; right++) {
            product *= nums[right];             // grow
            while (product >= k) {              // shrink until the product is below k
                product /= nums[left];
                left++;
            }
            count += right - left + 1;          // every window ending at right, starting at left or later
        }
        return count;
    }
}

var numSubarrayProductLessThanK = function(nums, k) {
    if (k <= 1) return 0;                       // every number is at least 1, so no product is below 1
    let product = 1, left = 0, count = 0;
    for (let right = 0; right < nums.length; right++) {
        product *= nums[right];                 // grow
        while (product >= k) {                  // shrink until the product is below k
            product /= nums[left];
            left++;
        }
        count += right - left + 1;              // every window ending at right, starting at left or later
    }
    return count;
};

Complexity Analysis

Time Complexity: O(n)

right moves n times and left at most n times, and neither moves back.

Space Complexity: O(1)

The product is always below k × 1000 = 10^9, so it fits in a 64-bit number (the code uses one anyway).

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Adding right - left. count += right - left

On nums = [10, 5, 2, 6], k = 100 it returns 4; the answer is 8. The windows that end at right start at left, left + 1, …, right: that's right − left + 1 of them. right - left forgets the one that is just nums[right] on its own.

No guard for k ≤ 1. while product >= k: # with k = 0 this never stops

On nums = [1, 2, 3], k = 0 it crashes with IndexError: list index out of range; the answer is 0. Every number is at least 1, so no product is ever below 1. Without returning 0 first, the shrink never gets the product under k, and left runs off the end of the array.

Shrinking only once per step. if product >= k:

On nums = [2, 2, 2, 100], k = 50 it returns 9; the answer is 6. One large number can push the product far past k, and dropping a single number from the left may not be enough. Until the product is below k, the windows ending at right don't count: shrink with while.

Where This Pattern Is Taught

This problem practises counting subarrays with a sliding window: each step adds the right − left + 1 windows that end at right. It's taught in Counting Subarrays with a Sliding Window.