2302. Count Subarrays With Score Less Than K
url: https://leetcode.com/problems/count-subarrays-with-score-less-than-k/description/
Input: nums = [2,1,4,3,5], k = 10
Output: 6
Explanation:
The 6 subarrays having scores less than 10 are:
- [2] with score 2 * 1 = 2.
- [1] with score 1 * 1 = 1.
- [4] with score 4 * 1 = 4.
- [3] with score 3 * 1 = 3.
- [5] with score 5 * 1 = 5.
- [2,1] with score (2 + 1) * 2 = 6.
💡 Note that subarrays such as [1,4] and [4,3,5] are not considered because their scores are 10 and 36 respectively, while we need scores strictly less than 10.
💻 Code
Approach :
- Sliding Window ✅
- left & right
- Calculation for this problem is:
(sum of elements) $*$ (length of the elements) $< k$ - A subarray is a contiguous sequence
Return: How many possibilities?
1. Solution
- TC : $O(n)$
- SC: $O(1)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def countSubarrays(self, nums: List[int], k: int) -> int:
cnt = 0
current_sum = 0
left = 0
n = len(nums)
for right in range(n):
current_sum += nums[right]
# shirink the window by moving the left pointer
# until the sum is less than k.
# if it is less than k, increment the count.
while current_sum * (right - left + 1) >= k:
current_sum -= nums[left]
left += 1
cnt += right - left + 1
return cnt
This problem is about the sliding window. Thus, left and right pointers are moving as needed. In this solution, it calculates for the current index first and then decides by keeping with counting or deducting the most left element.
💡 The important thing to be considered is the time complex. It can be considered as $O(n^2)$, but $O(n)$ in my solution. Let’s think about using amortized analysis. The outer for loop runs in $n$ times, and the inner while loop runs at most $n$ times in a worst case. Thus, the inner loop only visits each element once as necessary. In other words, the inner loop never goes up more than $n$ times.