Counting Subarrays With a Product Less Than k

The Problem: "Product Conundrum"

You are given an array of positive whole numbers called arr, and one more number called k. Your job is to count how many contiguous subarrays have a product that is strictly less than k.

Let's slow down and make sure every word here is clear.

What is a "contiguous subarray"?

A subarray is just a piece of the array that you cut out without skipping anything. The numbers must sit next to each other in the original array.

For example, if arr = [10, 5, 2, 6], then:

• [5, 2] is a valid subarray (5 and 2 are neighbors).
• [10, 6] is not a valid subarray, because 10 and 6 are not next to each other — you skipped over 5 and 2.

So "contiguous" simply means "in one unbroken stretch."

What does "product" mean?

The product is what you get when you multiply all the numbers in the subarray together.

• Product of [5, 2] = 5 * 2 = 10.
• Product of [10, 5, 2] = 10 * 5 * 2 = 100.

What does "strictly less than k" mean?

"Strictly less than" means the product must be smaller than k. It is not allowed to be equal to k.

• If k = 100, then a product of 99 counts (99 < 100). ✅
• A product of 100 does not count, because 100 is equal to k, not less than it. ❌

This little detail is important and it is exactly where many people make mistakes.

Walking Through Example 1

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

Output: 8

We need to find every contiguous subarray whose product is below 100. Let's check them one group at a time.

Subarrays of length 1 (just single numbers):

• [10] → product 10 → 10 < 100 ✅
• [5] → product 5 → ✅
• [2] → product 2 → ✅
• [6] → product 6 → ✅

That is 4 so far.

Subarrays of length 2:

• [10, 5] → product 50 → ✅
• [5, 2] → product 10 → ✅
• [2, 6] → product 12 → ✅

Now we are at 7.

Subarrays of length 3:

• [10, 5, 2] → product 100 → not counted, because 100 is not less than 100. ❌
• [5, 2, 6] → product 60 → ✅

That gives us 1 more, so 8 in total.

Subarrays of length 4:

• [10, 5, 2, 6] → product 600 → far too big. ❌

So the final answer is 8. Notice how [10, 5, 2] was the trap: its product hit exactly 100, so it was thrown out.

Walking Through Example 2

Input: arr = [10, 5], k = 50

Output: 2

• [10] → product 10 → ✅
• [5] → product 5 → ✅
• [10, 5] → product 50 → 50 is not less than 50 ❌

Only the two single-element subarrays qualify, so the answer is 2.

The Big Idea Behind Solving It

The slow way is to check every possible subarray, multiply its numbers, and compare to k. That works, but it is wasteful.

A smarter idea uses a window — think of it as a sliding box over the array. You grow the box on the right by adding a new number. If the product inside the box ever reaches k or more, you shrink the box from the left (divide the product by the number you remove) until the product is below k again. At each step, the size of the valid box tells you how many new subarrays end at that position. Because all numbers here are positive, multiplying always grows the product and dividing always shrinks it, which is what makes this window trick safe to use.

The starter code gives you a function to fill in:

class Solution {
public:
    int productConundrum(vector<int> &arr, in...
};

You write the logic inside this function and return the final count.