# Subarray Product Less Than K
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/subarray-product-less-than-k)
Canonical: https://scaleengineer.com/dsa/problems/subarray-product-less-than-k
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [Agoda](https://scaleengineer.com/companies/agoda), [Airbnb](https://scaleengineer.com/companies/airbnb), [IBM](https://scaleengineer.com/companies/ibm), [Nvidia](https://scaleengineer.com/companies/nvidia), [PayPal](https://scaleengineer.com/companies/paypal), [Samsung](https://scaleengineer.com/companies/samsung), [ServiceNow](https://scaleengineer.com/companies/servicenow), [SoFi](https://scaleengineer.com/companies/sofi), [Wise](https://scaleengineer.com/companies/wise), [Salesforce](https://scaleengineer.com/companies/salesforce), [Flexport](https://scaleengineer.com/companies/flexport)
---
## 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`.

**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`

# Approaches
## Brute Force
This approach involves generating every possible contiguous subarray, calculating the product of its elements, and counting how many of these products are strictly less than `k`. It is the most straightforward but also the least efficient method.
**Time:** O(N^2), where N is the length of the `nums` array. The two nested loops lead to a quadratic number of product calculations in the worst case. · **Space:** O(1), as we only use a constant amount of extra space for variables like the counter and the running product.
**Pros:** Simple to understand and implement.; Correct for any valid input, assuming it runs within the time limit.
**Cons:** Highly inefficient due to its quadratic time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode for the given constraints.
### Explanation
The brute-force method systematically checks every single contiguous subarray. We use two nested loops to achieve this. The outer loop selects a starting index `i`, and the inner loop selects an ending index `j`. For each subarray `nums[i...j]`, we compute its product. If this product is less than `k`, we increment a counter. A small optimization is included: once the product for a subarray starting at `i` exceeds `k`, we can stop extending it (break the inner loop), as adding more positive numbers will only increase the product further.

```java
class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) {
            return 0;
        }
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            long product = 1;
            for (int j = i; j < nums.length; j++) {
                product *= nums[j];
                if (product < k) {
                    count++;
                } else {
                    break; // Optimization
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Iterate through the array with an outer loop using index `i` from 0 to `n-1`. This `i` will be the starting point of the subarray.
- Inside the outer loop, start an inner loop with index `j` from `i` to `n-1`. This `j` will be the ending point of the subarray.
- For each subarray `nums[i...j]`, calculate the product of its elements. Initialize a variable `product` to 1 before the inner loop (for each `i`).
- In the inner loop, multiply `product` by `nums[j]`.
- If the `product` is strictly less than `k`, increment the `count`.
- If the `product` becomes greater than or equal to `k`, we can break the inner loop because all subsequent subarrays starting at `i` will also have a product greater than or equal to `k` (since all numbers are positive).
- After iterating through all possible start and end points, return `count`.

## Sliding Window
A much more efficient solution can be achieved using the sliding window technique. This approach maintains a dynamic window (a contiguous subarray) and expands or shrinks it to ensure the product of its elements remains less than `k`, counting valid subarrays in a single pass.
**Time:** O(N), where N is the length of `nums`. Each element is visited at most twice: once by the `right` pointer and once by the `left` pointer. This results in a single pass over the array. · **Space:** O(1), as it only requires a few variables (`left`, `right`, `product`, `count`) to keep track of the window and the result.
**Pros:** Optimal time complexity, making it very efficient for large inputs.; Constant space complexity.; Effectively avoids re-computation by reusing the product of the previous window.
**Cons:** Can be slightly less intuitive to devise compared to the brute-force approach.
### Explanation
The sliding window approach is optimal for this problem. We use two pointers, `left` and `right`, to define the boundaries of our window. The `right` pointer always moves forward, expanding the window by including a new element. We keep track of the product of elements within the current window `[left, right]`.

As we expand the window to the right by multiplying with `nums[right]`, the product might become greater than or equal to `k`. When this happens, we must shrink the window from the left by dividing the product by `nums[left]` and incrementing the `left` pointer. We repeat this shrinking process until the window's product is strictly less than `k` again.

For any valid window `[left, right]`, all subarrays ending at `right` are also valid. These are `[nums[right]]`, `[nums[right-1], nums[right]]`, ..., `[nums[left], ..., nums[right]]`. The number of such subarrays is `right - left + 1`. By adding this quantity to our total count at each step of the `right` pointer's iteration, we efficiently count all valid subarrays.

```java
class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) {
            return 0;
        }
        int count = 0;
        long product = 1;
        int left = 0;
        for (int right = 0; right < nums.length; right++) {
            product *= nums[right];
            while (product >= k) {
                product /= nums[left];
                left++;
            }
            // Every subarray ending at 'right' with a start in [left, right] is valid.
            count += right - left + 1;
        }
        return count;
    }
}
```
### Algorithm
- Handle the edge case: if `k <= 1`, return 0, as all numbers in `nums` are positive and >= 1.
- Initialize `count = 0`, `left = 0`, and `product = 1` (using a `long` data type to prevent potential overflow).
- Iterate through the array with a `right` pointer from `0` to `n-1`.
-  In each iteration, expand the window by multiplying `product` by `nums[right]`.
-  Use a `while` loop to shrink the window from the left: while `product >= k`, divide `product` by `nums[left]` and increment `left`.
-  After the window is valid (product < k), the number of new subarrays ending at `right` is `right - left + 1`. Add this to `count`.
-  Continue until `right` has traversed the entire array.
- Return `count`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int NumSubarrayProductLessThanK(int[] nums, int k) {
        int ans = 0, l = 0;
        int p = 1;
        for (int r = 0; r < nums.Length; ++r) {
            p *= nums[r];
            while (l <= r && p >= k) {
                p /= nums[l++];
            }
            ans += r - l + 1;
        }
        return ans;
    }
}
```

### Java

```java
class Solution {
public
  int numSubarrayProductLessThanK(int[] nums, int k) {
    int ans = 0;
    for (int i = 0, j = 0, s = 1; i < nums.length; ++i) {
      s *= nums[i];
      while (j <= i && s >= k) {
        s /= nums[j++];
      }
      ans += i - j + 1;
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @param {number} k * @return {number} */ var numSubarrayProductLessThanK =
  function (nums, k) {
    const n = nums.length;
    let ans = 0;
    let s = 1;
    for (let i = 0, j = 0; i < n; ++i) {
      s *= nums[i];
      while (j <= i && s >= k) {
        s = Math.floor(s / nums[j++]);
      }
      ans += i - j + 1;
    }
    return ans;
  };

```

### CPP

```cpp
class Solution { public: int numSubarrayProductLessThanK ( vector < int >& nums , int k ) { int ans = 0 ; for ( int i = 0 , j = 0 , s = 1 ; i < nums . size (); ++ i ) { s *= nums [ i ]; while ( j <= i && s >= k ) s /= nums [ j ++ ]; ans += i - j + 1 ; } return ans ; } };
```

### Python

```python
class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int: ans, s, j = 0, 1, 0 for i, v in enumerate(nums): s *= v while j <= i and s >= k: s //= nums[j] j += 1 ans += i - j + 1 return ans

```