Problem

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.

Examples

Example 1

1
2
3
4
5

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

1
2

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

Solution

Method 1 - Generate subarray using nested array and varying size

Iterate through all possible subarrays using two nested loops. You can read more here: Print all subarrays of a given array. For each subarray, calculate the product of its elements. If the product is less than k, increment the count. This brute-force approach checks every possible subarray.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
  public int numSubarrayProductLessThanK(int[] nums, int k) {
    if (k <= 1) return 0;
    int prod = 1, result = 0, left = 0;
    for (int right = 0; right < nums.length; right++) {
      prod *= nums[right];
      while (prod >= k) {
        prod /= nums[left++];
      }
      result += right - left + 1;
    }
    return result;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

from typing import List

class Solution:
  def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
    if k <= 1:
      return 0
    prod = 1
    result = 0
    left = 0
    for right, val in enumerate(nums):
      prod *= val
      while prod >= k:
        prod //= nums[left]
        left += 1
      result += right - left + 1
    return result

Complexity

  • ⏰ Time complexity: O(n^3)
  • 🧺 Space complexity: O(1)

Method 2 - Using Sliding Window Technique

Let’s solve this problem using the sliding window approach. The idea is to maintain a window with a product less than k and expand it by moving the right pointer. If the product becomes greater than or equal to k, move the left pointer to reduce the product. For each position of the right pointer, the number of valid subarrays ending at that position is right - left + 1.

Whenever a new element is added to the current subarray, the product may either stay below k or reach/exceed k.

  • Begin with the first element and keep extending the window as long as the product remains less than k.
  • If the product becomes too large, move the left pointer forward and divide out elements from the product until it is less than k again.

Continue this process throughout the array.

To count valid subarrays: If the product for the current window is less than k, then every subarray ending at the current position and starting from any index within the window is valid. For example, if the window has 4 elements and the product is still less than k, there are 4 new valid subarrays ending at this position.

Dry Run

For nums = [10, 4, 2, 6] and k = 100:

  • Window [10]: product = 10 < 100, count = 1
  • Window [10, 4]: product = 40 < 100, count = 3 (adds [10,4], [4])
  • Window [10, 4, 2]: product = 80 < 100, count = 6 (adds [10,4,2], [4,2], [2])
  • Window [10, 4, 2, 6]: product = 480 > 100, remove 10, window [4,2,6]: product = 48 < 100, count = 9

This way, all valid subarrays are counted efficiently.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
  public int numSubarrayProductLessThanK(int[] nums, int k) {
    if (k <= 1) return 0;
    int prod = 1, result = 0, left = 0;
    for (int right = 0; right < nums.length; right++) {
      prod *= nums[right];
      while (prod >= k) {
        prod /= nums[left++];
      }
      result += right - left + 1;
    }
    return result;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

from typing import List

class Solution:
  def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
    if k <= 1:
      return 0
    prod = 1
    result = 0
    left = 0
    for right, val in enumerate(nums):
      prod *= val
      while prod >= k:
        prod //= nums[left]
        left += 1
      result += right - left + 1
    return result

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)