Subarray Product Less Than K

Subarray Product Less Than K

What is this problem about?

The "Subarray Product Less Than K" interview question asks you to count the number of contiguous subarrays whose product is strictly less than a given integer k. For example, given an array of positive integers [10, 5, 2, 6] and k = 100, you need to find all subarrays like [10], [5], [10, 5], etc., that satisfy the condition. This problem is particularly interesting because it deals with products, which can grow very quickly.

Why is this asked in interviews?

This question is a favorite at companies like Apple, Microsoft, and Google because it is a perfect candidate for the sliding window technique. It tests whether a candidate can optimize an O(n^2) brute-force solution down to O(n) time complexity. It also requires careful handling of edge cases, such as when k is 0 or 1, where no product of positive integers can be less than k.

Algorithmic pattern used

The most efficient pattern for this problem is the Sliding Window (Two Pointers). You maintain a "window" of elements whose product is less than k. As you expand the window by moving the right pointer, you multiply the current product. If the product becomes greater than or equal to k, you shrink the window from the left until the product is back within the limit. For each right pointer position, the number of new valid subarrays added is right - left + 1.

Example explanation (use your own example)

Array: [2, 3, 5], k = 15.

1. Right=0, val=2: Product=2. Valid subarrays ending at index 0: [2]. Total = 1.
2. Right=1, val=3: Product=2*3=6. Valid subarrays ending at index 1: [3], [2, 3]. Total = 1 + 2 = 3.
3. Right=2, val=5: Product=6*5=30. Not less than 15.
   • Shrink left: Remove 2. Product=15. Still not less than 15.
   • Shrink left: Remove 3. Product=5. Now less than 15.
   • Valid subarrays ending at index 2: [5]. Total = 3 + 1 = 4. Final count: 4.

Common mistakes candidates make

The most common mistake is not correctly counting the subarrays. Many candidates forget that right - left + 1 represents the number of valid subarrays ending at the current right pointer. Another frequent error is failing to handle k <= 1. Since the array contains only positive integers, a product of 1 or more can never be strictly less than 1. Forgetting to check this can lead to an infinite loop or incorrect results.

Interview preparation tip

When practicing the Subarray Product Less Than K interview pattern, focus on the "expansion and contraction" logic of the sliding window. Be ready to explain why the right - left + 1 formula works—it's because adding a new element to a valid window creates exactly that many new subarrays. Also, mention the O(n) time and O(1) space complexity to demonstrate your optimization skills.