Practice/Apple/Leetcode 713. Subarray Product Less Than K

Leetcode 713. Subarray Product Less Than K

CodingMust

Problem

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

A subarray is a contiguous sequence of elements within an array. For example, in the array [1, 2, 3], the subarrays are [1], [2], [3], [1, 2], [2, 3], and [1, 2, 3].

Requirements

1. Count all contiguous subarrays whose product is strictly less than k
2. All elements in nums are positive integers (greater than 0)
3. Return the total count as an integer
4. Handle edge cases where k is very small or when no valid subarrays exist

Constraints

• 1 ≤= nums.length ≤= 30,000
• 1 ≤= nums[i] ≤= 1,000
• 0 ≤= k ≤= 1,000,000
• Target time complexity: O(n) where n is the length of the array
• Target space complexity: O(1)

Examples

Example 1:

Input: nums = [10, 5, 2, 6], k = 100 Output: 8 Explanation: The 8 subarrays with product < 100 are: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6] Note that [10,5,2] has product 100, which is not strictly less than k.

Example 2:

Input: nums = [1, 2, 3], k = 0 Output: 0 Explanation: Since k = 0 and all numbers are positive, no subarray can have a product less than 0.

Example 3:

Input: nums = [1, 1, 1], k = 2 Output: 6 Explanation: All possible subarrays have product 1, which is less than 2: [1] (appears 3 times), [1,1] (appears 2 times), [1,1,1] (appears 1 time) Total: 3 + 2 + 1 = 6