Subarray Product Less Than K

IF
AlgoAxiomStaff Engineers
JSTS
Medium20 mins

Given an array of positive integers nums and an integer k, return the number of contiguous subarrays where the product of all the elements is strictly less than k.

Examples

Input: nums = [10, 5, 2, 6], k = 100

Output: 8

Explanation: The 8 subarrays with product less than 100 are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]. Note that [10, 5, 2] is not included because the product (100) is not strictly less than k.

Input: nums = [1, 2, 3], k = 0

Output: 0

Explanation: No subarray has a product less than 0 since all elements are positive.

Input: nums = [1, 1, 1], k = 2

Output: 6

Explanation: All 6 subarrays have a product of 1, which is less than 2: [1], [1], [1], [1,1], [1,1], [1,1,1].

Constraints

  • 1 <= nums.length <= 3 * 10^4
  • 1 <= nums[i] <= 1000
  • 0 <= k <= 10^6
Source: Sliding Window pattern — AlgoAxiom
JavaScript
Test Case 1
root = [1, 2, 3]
Test Case 2
root = [1, 2, 3, 4, 5]
Idle