Count Subarrays With Score Less Than K - Leetcode Solution

Problem Statement:

Given an array of integers nums and an integer k, return the number of subarrays of nums that have a score less than or equal to k.

The score of a subarray is the sum of its elements.

Solution:

We can solve this problem using sliding window method. We will maintain two pointers l and r to track the start and end of the window respectively. We will also maintain the current sum of the window.

Initially, l=r=0 and the current sum is nums[0]. We will then keep on increasing r until the current sum is less than or equal to k. Once the current sum becomes greater than k, we will move the left pointer to the right until the current sum becomes less than or equal to k again. In each step, we will update the count of the subarrays whose score is less than or equal to k.

Let's see the code for the same:

int subarrayLessThanK(vector<int>& nums, int k) { int l=0,r=0,sum=nums[0],count=0; while(r<nums.size()){ if(sum<=k){ count+=(r-l+1); r++; if(r<nums.size()) sum+=nums[r]; } else{ sum-=nums[l]; l++; } } return count; }

Time Complexity: O(n)

Space Complexity: O(1)

Explanation:

We have initialised l=0, r=0 and sum=nums[0]. We will then keep on increasing r until the current sum is less than or equal to k. We will also update the count of subarrays in each step.

If the current sum is less than or equal to k, we will add (r-l+1) to the count of subarrays. r will be incremented and sum will be updated accordingly.

If the current sum becomes greater than k, we will move the left pointer to the right until the current sum becomes less than or equal to k again. In each step, we will subtract nums[l] from the sum and increment l.

Finally, we will return the count of subarrays whose score is less than or equal to k.

Example:

Let's take an example to understand this solution better:

nums=[2,3,4,1,5], k=7

Initially, l=0, r=0 and sum=nums[0]=2.

We will then keep on increasing r until the current sum is less than or equal to k. At r=2, the current sum becomes 9 which is greater than k. We will then move the l pointer to the right and update the sum accordingly. After l=1, the sum becomes 7 which is less than or equal to k. We will add 2 subarrays to the count of subarrays, i.e. [2,3] and [3]. We will then keep on increasing r until the current sum is greater than k again. At r=4, the current sum becomes 15 which is greater than k. We will then move the l pointer to the right and update the sum accordingly. After l=2, the sum becomes 8 which is less than or equal to k. We will add 2 subarrays to the count of subarrays, i.e. [4,1,5] and [1,5]. Finally, we will return the count which is 4.

Hence, the solution is correct and complete.

1