Count Subarrays With Score Less Than K: The score of an array is defined as the product of its sum and its length.
- For example, the score of
[1, 2, 3, 4, 5]
is(1 + 2 + 3 + 4 + 5) * 5 = 75
.
Given a positive integer array nums
and an integer k
, return the number of non-empty subarrays of nums
whose score is strictly less than k
.
A subarray is a contiguous sequence of elements within an array.
Example 1:
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.
Example 2:
Input: nums = [1,1,1], k = 5 Output: 5 Explanation: Every subarray except [1,1,1] has a score less than 5. [1,1,1] has a score (1 + 1 + 1) * 3 = 9, which is greater than 5. Thus, there are 5 subarrays having scores less than 5.
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 105
1 <= k <= 1015
Solution:
Subarrays + Less Than K = Slide Window
Explanation
Maintain a sliding window from A[i] to A[j]
, with a score less than k
.cur
counts the current sum of elements between the windows.
Iterate j
from 0
to A.length - 1
,
each round we firstly add A[j]
to the window,
update cur += A[j]
.
The current sum is cur
and length is j - i + 1
,
If the score cur * (j - i + 1) >= k
,
the window is too big,
we remove A[i]
and update i++
.
We continue doing this until the score is less than k
.
Then we find the smallest i
where subarray A[i]
to A[j]
has scored less than k.
For any subarray ending at A[j] with a shorter length, they have scored less than k.
There are j – i + 1 subarrays in total, so we update the result res += j - i + 1
Complexity
Time O(n)
Space O(1)
Runtime: 3 ms
, faster than 100.00%
of Java online submissions for Count Subarrays With Score Less Than K.
Memory Usage: 52 MB
, less than 83.33%
of Java online submissions for Count Subarrays With Score Less Than K.
public long countSubarrays(int[] A, long k) {
long res = 0, cur = 0;
for (int j = 0, i = 0; j < A.length; ++j) {
cur += A[j];
while (cur * (j - i + 1) >= k)
cur -= A[i++];
res += j - i + 1;
}
return res;
}
long long countSubarrays(vector<int>& A, long long k) {
long long res = 0, cur = 0;
for (int j = 0, i = 0; j < A.size(); ++j) {
cur += A[j];
while (cur * (j - i + 1) >= k)
cur -= A[i++];
res += j - i + 1;
}
return res;
}
def countSubarrays(self, A, k):
res = cur = i = 0
for j in range(len(A)):
cur += A[j]
while cur * (j - i + 1) >= k:
cur -= A[i]
i += 1
res += j - i + 1
return res
class Solution {
typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;
#define endl '\n'
static const ll mod = 1e9;
public:
long long countSubarrays(vector<int>& v, long long k) {
ll sz = v.size(), res = 0;
vi pre(sz);
pre[0] = v[0];
for (ll i = 1;i < sz;i++)
pre[i] = pre[i - 1] + v[i];
for (ll i = 0;i < sz;++i) {
ll l = i,
r = sz - 1,
ind = -1;
while (l <= r) {
ll mid = l + ((r - l) >> 1);
ll score = pre[mid] - (i > 0 ? pre[i - 1] : 0);
score *= mid - i + 1;
if (score < k) {
ind = mid;
l = mid + 1;
continue;
}
r = mid - 1;
}
if (ind != -1)
res += ind - i + 1;
}
return res;
}
};
Happy Learning – If you require any further information, feel free to contact me.