# Easy Understand Sliding window solution O(N)

• Honestly, the first approach I tried is DFS, which leads to TLE.
Then I came up with this sliding window solution. See the solution below:

1. Expand the window as large as possible;
2. Compute the number of valid subarray.
``````class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
int p = 0;
int product = 1;
int sum = 0;

for (int i = 0; i < nums.length; i++) {
if (p < i) p = i;

while (p < nums.length && nums[p] * product < k) {
product *= nums[p];
p++;
}

sum += p - i;

if (p != i) product /= nums[i];
}

return sum;
}
}
``````

• Hi, thank you for your answer but this solution failed at following test case,
[1,6,1,6,1]
5
The reason is that when i == p,

``````product /= nums[i];
``````

actually, nums[i] has not been multiplied by the product so dividing the product by nums[i] will cause an error. I add a condition

``````if (p != i) {
product /= nums[i];
}
``````

then it passed.

thx.

• @wangh23 Thanks for your response. I think you are totally right and I have updated my code.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.