Easy Understand Sliding window solution O(N)

  • 0

    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];
                sum += p - i;
                if (p != i) product /= nums[i];
            return sum;

  • 0

    Hi, thank you for your answer but this solution failed at following test case,
    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.


  • 0

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

Log in to reply

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