Subarray Product Less Than K
Asked at Apple
Problem
Given an array of positive integers nums and an integer k, count the number of contiguous subarrays where the product of all elements is strictly less than k.
Asked At
| Company | Difficulty | |
|---|---|---|
| Apple | MEDIUM | View all Apple questions → |
How to Think About It
Brute force: for each starting index, extend the subarray and multiply until product >= k, counting valid subarrays.
Prefix product array with binary search for each starting position.
Sliding window: maintain a window where the product is less than k, expanding and contracting as needed.
For each valid window [left, right], the number of subarrays ending at right is (right - left + 1).
Optimal: use a sliding window with two pointers, adding (right - left + 1) to the count when the window is valid.
Optimal Approach
Use a sliding window with two pointers. Maintain a running product. For each new element at the right pointer, multiply it into the product. While the product is >= k, divide out the element at the left pointer and advance left. If the window is valid (product < k), all subarrays ending at the right index are valid, so add (right - left + 1) to the count. This works because all numbers are positive, so the product is monotonic within the window.
What Trips People Up in Real Interviews
The product constraint is strict: product must be strictly less than k.
Since all numbers are positive, the product only grows when extending the window.
When product >= k, shrink from the left until the product is valid again.
Count formula: for a valid window [left, right], add (right - left + 1) new subarrays.
Handle edge case where k <= 1 — no subarray can have product less than k for positive integers.
Solution Code
def numSubarrayProductLessThanK(nums, k):
if k <= 1:
return 0
count = 0
product = 1
left = 0
for right in range(len(nums)):
product *= nums[right]
while product >= k:
product //= nums[left]
left += 1
count += right - left + 1
return countFrequently Asked Questions
What is the Subarray Product Less Than K problem?
Given an array of positive integers nums and an integer k, count the number of contiguous subarrays where the product of all elements is strictly less than k.
How do you solve Subarray Product Less Than K?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Subarray Product Less Than K?
Subarray Product Less Than K is asked at Apple. It is a medium difficulty problem.
What are common mistakes on Subarray Product Less Than K?
- The product constraint is strict: product must be strictly less than k.
- Since all numbers are positive, the product only grows when extending the window.
- When product >= k, shrink from the left until the product is valid again.
- Count formula: for a valid window [left, right], add (right - left + 1) new subarrays.
- Handle edge case where k <= 1 — no subarray can have product less than k for positive integers.