# LeetCode 713: Subarray Product Less Than K

## Problem Restatement

We are given an integer array `nums` and an integer `k`.

We need to count how many contiguous subarrays have product strictly less than `k`.

A subarray must be contiguous. That means we can take a continuous segment of the array, not arbitrary elements.

For example:

```python
nums = [10, 5, 2, 6]
k = 100
```

The valid subarrays are:

```python
[10]
[5]
[2]
[6]
[10, 5]
[5, 2]
[2, 6]
[5, 2, 6]
```

There are `8` valid subarrays.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `nums` |
| Input | Integer `k` |
| Output | Number of contiguous subarrays with product less than `k` |
| Condition | Product must be strictly less than `k` |
| Important detail | Subarrays must be contiguous |

The function shape is:

```python
class Solution:
    def numSubarrayProductLessThanK(self, nums: list[int], k: int) -> int:
        ...
```

## Examples

Example 1:

```python
nums = [10, 5, 2, 6]
k = 100
```

Valid subarrays:

```python
[10]
[5]
[2]
[6]
[10, 5]
[5, 2]
[2, 6]
[5, 2, 6]
```

Output:

```python
8
```

Example 2:

```python
nums = [1, 2, 3]
k = 0
```

All numbers are positive, so every subarray product is at least `1`.

No product can be less than `0`.

Output:

```python
0
```

## First Thought: Check Every Subarray

A direct approach is to enumerate every subarray.

For each start index `i`, multiply values from `i` to every possible end index `j`.

Whenever the product is less than `k`, count it.

```python
class Solution:
    def numSubarrayProductLessThanK(self, nums: list[int], k: int) -> int:
        count = 0

        for i in range(len(nums)):
            product = 1

            for j in range(i, len(nums)):
                product *= nums[j]

                if product < k:
                    count += 1
                else:
                    break

        return count
```

This works because all values in `nums` are positive, so once the product reaches `k` or more, extending the subarray can only keep it the same or make it larger.

## Problem With Brute Force

The brute force method can still examine many subarrays.

If the array has `n` elements, the number of contiguous subarrays is:

```python
n * (n + 1) / 2
```

So the worst-case time is:

```python
O(n^2)
```

We need a faster method.

## Key Insight

Because all numbers are positive, we can use a sliding window.

Maintain a window:

```python
nums[left:right + 1]
```

and its product.

For every `right`, expand the window by multiplying `nums[right]`.

If the product becomes greater than or equal to `k`, move `left` rightward and divide out `nums[left]` until the product is less than `k` again.

Once the window product is less than `k`, every subarray ending at `right` and starting between `left` and `right` is valid.

The number of such subarrays is:

```python
right - left + 1
```

For example, suppose the current valid window is:

```python
[5, 2, 6]
```

ending at `6`.

The valid subarrays ending at `6` are:

```python
[6]
[2, 6]
[5, 2, 6]
```

There are `3`, equal to the window length.

## Algorithm

Handle small `k` first.

Since every number in `nums` is positive, if:

```python
k <= 1
```

then no subarray can have product less than `k`.

Return `0`.

Otherwise:

1. Set `left = 0`.
2. Set `product = 1`.
3. Set `count = 0`.
4. For each `right` from `0` to `len(nums) - 1`:
   - Multiply `product` by `nums[right]`.
   - While `product >= k`, divide by `nums[left]` and increment `left`.
   - Add `right - left + 1` to `count`.
5. Return `count`.

## Correctness

The algorithm maintains the invariant that after the while loop finishes, the window from `left` to `right` has product less than `k`.

When we extend the window by including `nums[right]`, the product may become too large. Since all numbers are positive, removing elements from the left decreases or preserves the product. The while loop keeps removing leftmost elements until the product is less than `k`.

After this adjustment, the full window `nums[left:right + 1]` has product less than `k`.

Now consider any subarray ending at `right` whose start index is between `left` and `right`. This subarray is formed by removing zero or more elements from the left side of a valid positive-product window. Removing positive factors cannot increase the product, so each of these subarrays also has product less than `k`.

There are exactly `right - left + 1` such subarrays.

Any subarray ending at `right` and starting before `left` is invalid, because `left` was advanced until the product became valid. Therefore the algorithm counts exactly all valid subarrays ending at each `right`.

Summing over all `right` counts every valid subarray exactly once, according to its ending index.

## Complexity

Let `n` be the length of `nums`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each index enters and leaves the window at most once |
| Space | `O(1)` | Only counters and pointers are used |

## Implementation

```python
class Solution:
    def numSubarrayProductLessThanK(self, nums: list[int], k: int) -> int:
        if k <= 1:
            return 0

        left = 0
        product = 1
        count = 0

        for right, value in enumerate(nums):
            product *= value

            while product >= k:
                product //= nums[left]
                left += 1

            count += right - left + 1

        return count
```

## Code Explanation

The early return handles the impossible case:

```python
if k <= 1:
    return 0
```

All numbers are positive, so every non-empty subarray product is at least `1`.

We initialize the sliding window:

```python
left = 0
product = 1
count = 0
```

Then we extend the right side:

```python
for right, value in enumerate(nums):
    product *= value
```

If the product is too large, shrink from the left:

```python
while product >= k:
    product //= nums[left]
    left += 1
```

After this loop, the current window product is less than `k`.

All valid subarrays ending at `right` are counted by:

```python
count += right - left + 1
```

Finally:

```python
return count
```

## Example Walkthrough

Use:

```python
nums = [10, 5, 2, 6]
k = 100
```

Start with:

```python
left = 0
product = 1
count = 0
```

At `right = 0`, value `10`:

```python
product = 10
```

Window `[10]` is valid.

Add:

```python
right - left + 1 = 1
```

Count is `1`.

At `right = 1`, value `5`:

```python
product = 50
```

Window `[10, 5]` is valid.

Valid subarrays ending here:

```python
[5]
[10, 5]
```

Add `2`.

Count is `3`.

At `right = 2`, value `2`:

```python
product = 100
```

This is not valid because the condition is strictly less than `100`.

Shrink from the left:

```python
product = 100 // 10 = 10
left = 1
```

Window `[5, 2]` is valid.

Valid subarrays ending here:

```python
[2]
[5, 2]
```

Add `2`.

Count is `5`.

At `right = 3`, value `6`:

```python
product = 60
```

Window `[5, 2, 6]` is valid.

Valid subarrays ending here:

```python
[6]
[2, 6]
[5, 2, 6]
```

Add `3`.

Final count is:

```python
8
```

## Testing

```python
def test_num_subarray_product_less_than_k():
    s = Solution()

    assert s.numSubarrayProductLessThanK([10, 5, 2, 6], 100) == 8
    assert s.numSubarrayProductLessThanK([1, 2, 3], 0) == 0
    assert s.numSubarrayProductLessThanK([1, 1, 1], 2) == 6
    assert s.numSubarrayProductLessThanK([100], 100) == 0
    assert s.numSubarrayProductLessThanK([99], 100) == 1
    assert s.numSubarrayProductLessThanK([2, 5, 3, 10], 30) == 6

    print("all tests passed")

test_num_subarray_product_less_than_k()
```

Test coverage:

| Test | Why |
|---|---|
| Standard example | Confirms sliding window count |
| `k = 0` | Confirms early return |
| All ones | Confirms many overlapping valid subarrays |
| Product equals `k` | Confirms strict inequality |
| Single valid element | Confirms minimum array behavior |
| Mixed values | Confirms repeated shrinking works |