Coding questions · Bloomberg
Count subarrays with product under target
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.
Given an array of positive integers nums and an integer T > 1, return the number of contiguous subarrays whose product is strictly less than T. Provide an algorithm that runs in O(n) time with O(1) extra space beyond the input. Discuss edge cases such as T <= 1 and the presence of 1s in nums, and explain why your approach is correct.
Count Subarrays With Product Under Target
Given an array of positive integers nums and an integer T, return the number of contiguous subarrays whose product is strictly less than T.
Your algorithm should run in O(n) time and use O(1) extra space beyond the input.
Important edge cases:
- If
T <= 1, the answer is0because every subarray product of positive integers is at least1. - Arrays may contain
1s. This does not break the sliding-window approach, but it means the product may stay the same when the window expands.
Why a sliding window works: because all numbers are positive, multiplying by a new right-end element can only keep the product the same or increase it, and moving the left end rightward can only keep the product the same or decrease it. So we can maintain the smallest valid window ending at each position. If the current valid window is nums[left:right+1], then every subarray ending at right and starting anywhere from left to right is also valid, contributing right - left + 1 new subarrays.
Constraints
0 <= len(nums) <= 2000001 <= nums[i] <= 10^9Tmay be any integer- An
O(n)time,O(1)extra space solution is expected
Examples
Example 1
Input: ([10, 5, 2, 6], 100)
Output: 8
Explanation: The valid subarrays are [10], [10,5], [5], [5,2], [5,2,6], [2], [2,6], and [6].
Example 2
Input: ([1, 1, 1], 2)
Output: 6
Explanation: All contiguous subarrays have product 1, so all 3 * 4 / 2 = 6 subarrays are valid.
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?