visual walkthrough
Subarray Product Less Than K
Counting subarrays ending at each right index; a key counting trick.
The idea
All numbers are positive, so shrinking a window lowers its product and growing raises it. Keep the longest window ending at each position whose product is below k.
If a window of length L is valid, then all L subarrays ending at its right edge (starting anywhere inside) are valid too, so add L at each step.
Complexity
| approach | time | space |
|---|---|---|
| Try every start | O(n²) | O(1) |
| Sliding window | O(n) | O(1) |