{x}
blog image

Subarray Product Less Than K

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

 

Example 1:

Input: nums = [10,5,2,6], k = 100
Output: 8
Explanation: The 8 subarrays that have 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 as the product of 100 is not strictly less than k.

Example 2:

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

 

Constraints:

  • 1 <= nums.length <= 3 * 104
  • 1 <= nums[i] <= 1000
  • 0 <= k <= 106

Solution Explanation: Sliding Window Technique

This problem can be efficiently solved using a sliding window approach. The core idea is to maintain a window within the input array nums such that the product of all elements within the window is less than k. We expand the window to the right and contract it from the left as needed to satisfy this condition.

Algorithm:

  1. Initialization:

    • ans: A variable to store the count of subarrays whose product is less than k. Initialized to 0.
    • l: The left pointer of the sliding window. Initialized to 0.
    • r: The right pointer of the sliding window. Initialized to 0.
    • p: A variable to keep track of the product of elements within the current window. Initialized to 1.

  2. Iteration:

    • The outer loop iterates through the nums array using the right pointer r.
    • In each iteration:
      • The current element nums[r] is multiplied into p (the window product).
      • Window Contraction: If p becomes greater than or equal to k, we need to shrink the window from the left. The inner while loop repeatedly divides p by nums[l] (the leftmost element) and increments l until p is less than k again. This ensures that the window's product always remains less than k.
      • Counting Subarrays: Once the condition p < k is met, we know that all subarrays ending at index r and starting from index l satisfy the condition. The number of such subarrays is r - l + 1. This is added to ans.

  3. Return Value: Finally, ans (the total count of subarrays) is returned.

Time Complexity: O(n)

The algorithm iterates through the input array once (the outer loop). The inner while loop, although nested, executes a total of at most n times across all iterations because l can only increase to a maximum of n positions. Therefore, the overall time complexity is linear.

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space to store variables like ans, l, r, and p. The space usage does not depend on the input size.

Code Examples (Python):

The Python code provided in the original response is already a very efficient implementation of this sliding window technique. I will not replicate it here. The code in other languages provided is also correct and follows the same algorithm. They differ only in syntax.