Subarray Product Less Than K
Updated
Problem statement
You are given an array of positive integers nums and an integer k.
Return the number of contiguous subarrays whose product of all elements is strictly less than k. A subarray is a non-empty run of neighboring elements. Two subarrays at different positions count separately, even if they hold the same values.
Function
numSubarrayProductLessThanK(nums: int[], k: int) → intExamples
Example 1
nums = [10,5,2,6]k = 100return = 8The subarrays with a product less than 100 are [10], [10,5], [5], [5,2], [5,2,6], [2], [2,6], [6]. That is 8 subarrays.
A product equal to 100, as in [10,5,2], does not count, because it is not strictly less than 100.
Example 2
nums = [4,2,2,1]k = 8return = 7The subarrays with a product less than 8 are [4], [2], [2,2], [2,2,1], [2], [2,1], [1]. That is 7 subarrays.
A product equal to 8, as in [4,2], does not count, because it is not strictly less than 8.
Example 3
nums = [3,2,5]k = 1return = 0Every element is at least 1, so every product is at least 1, and no product can be less than 1. The answer is 0.
Constraints
1 <= nums.length <= 3 * 10^41 <= nums[i] <= 10000 <= k <= 10^6
More Angel One Phone Screen questions
Similar questions at other companies
- Subarray Product Less Than KApple · PHONE SCREENApple interview questions
- Subarray Product Less Than KThe D.E. Shaw Group · PHONE SCREENThe D.E. Shaw Group interview questions
- Max Consecutive Ones IIINykaa · PHONE SCREENNykaa interview questions
- Max Consecutive Ones IIIAmazon · PHONE SCREEN
- Compact Conversation History by Token BudgetSierra · PHONE SCREENSierra interview questions
- Shortest Window with Required CountsOracle · ONSITE INTERVIEWOracle interview questions
- Count Subarrays With Product Equal to KSalesforce · OASalesforce interview questions
- Longest Binary Window with at Most K OnesLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
- Count Hotspot Playback WindowsGoogle · ONSITE INTERVIEWGoogle interview questions
- Subarray with a Given SumExpedia · ONSITE INTERVIEWExpedia interview questions