Count subarrays with product under target
Company: Bloomberg
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Quick Answer: This question evaluates algorithmic problem-solving skills for array manipulation with multiplicative constraints, specifically reasoning about subarray products and boundary behaviors; it belongs to the Coding & Algorithms domain and emphasizes practical application of efficient, linear-time algorithm design rather than purely conceptual theory.
Constraints
- `0 <= len(nums) <= 200000`
- `1 <= nums[i] <= 10^9`
- `T` may be any integer
- An `O(n)` time, `O(1)` extra space solution is expected
Examples
Input: ([10, 5, 2, 6], 100)
Expected Output: 8
Explanation: The valid subarrays are [10], [10,5], [5], [5,2], [5,2,6], [2], [2,6], and [6].
Input: ([1, 1, 1], 2)
Expected Output: 6
Explanation: All contiguous subarrays have product 1, so all 3 * 4 / 2 = 6 subarrays are valid.
Input: ([1, 2, 3], 1)
Expected Output: 0
Explanation: Since all numbers are positive, every subarray product is at least 1, so none are strictly less than 1.
Input: ([], 10)
Expected Output: 0
Explanation: An empty array has no subarrays.
Input: ([100], 100)
Expected Output: 0
Explanation: The only subarray has product 100, which is not strictly less than 100.
Input: ([1, 2, 1, 1], 3)
Expected Output: 10
Explanation: Every contiguous subarray in this array has product 1 or 2, both of which are less than 3.
Solution
def solution(nums, T):
if T <= 1:
return 0
left = 0
product = 1
count = 0
for right in range(len(nums)):
product *= nums[right]
while left <= right and product >= T:
product //= nums[left]
left += 1
count += right - left + 1
return countTime complexity: O(n). Space complexity: O(1).
Hints
- Because all elements are positive, try maintaining a window whose product is always less than `T`.
- For each right endpoint, once the window is valid, how many different starting positions produce valid subarrays ending there?