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

  • 0
    W

    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.


  • 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.