aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-04-28 18:48:09 -0600
committerJack Sangdahl <[email protected]>2025-04-28 18:48:09 -0600
commit2e8743f0ebda2c02358ce0f124a754fcf9059668 (patch)
treeb337cd80935b671bccc697fab3a6222deb8abac6
parentc8dfd03864b524280c0c3c745e6a7c428b6bfe5b (diff)
downloadleetcode-2e8743f0ebda2c02358ce0f124a754fcf9059668.tar.gz
leetcode-2e8743f0ebda2c02358ce0f124a754fcf9059668.zip
2962. count subarrays where max element appears at least k times
-rw-r--r--count_subarr_max_elem_k.c20
-rw-r--r--count_subarr_max_elem_k.py16
2 files changed, 16 insertions, 20 deletions
diff --git a/count_subarr_max_elem_k.c b/count_subarr_max_elem_k.c
index e6bf5ad..4768843 100644
--- a/count_subarr_max_elem_k.c
+++ b/count_subarr_max_elem_k.c
@@ -9,19 +9,15 @@
*/
long long countSubarrays(int *nums, int numsSize, int k) {
- int max = 0, cnt = 0, idx[numsSize];
+ int max = -1, curr = 0;
long long ans = 0;
- for (int i = 0; i < numsSize; i++)
- max = max > nums[i];
- for (int i = 0; i < numsSize; i++)
- if (nums[i] == max)
- idx[cnt++] = i;
- for (int i = 0; i <= cnt - k; i++) {
- long long left = idx[i], right = idx[i + k - 1],
- bound = i - 1 >= 0 ? idx[i - 1] : -1;
- if (!i)
- bound = -1;
- ans += (left - bound) * (numsSize - right);
+ for (int i = 0; i < numsSize; ++i)
+ max = nums[i] > max ? nums[i] : max;
+ for (int l = 0, r = 0; r < numsSize; r++) {
+ curr += nums[r] == max;
+ while (curr >= k)
+ curr -= nums[l++] == max;
+ ans += l;
}
return ans;
}
diff --git a/count_subarr_max_elem_k.py b/count_subarr_max_elem_k.py
index 8f734f2..7852d49 100644
--- a/count_subarr_max_elem_k.py
+++ b/count_subarr_max_elem_k.py
@@ -15,18 +15,18 @@ class Solution(object):
:type k: int
:rtype: int
"""
+ ans, curr, l = 0, 0, 0
m = max(nums)
- ans, curr, i = 0, 0, 0
- for j in range(len(nums)):
- curr += nums[j] == m
+ for r in range(len(nums)):
+ curr += nums[r] == m
while curr >= k:
- curr -= nums[i] == m
- i += 1
- ans += i
+ curr -= nums[l] == m
+ l += 1
+ ans += l
return ans
if __name__ == "__main__":
obj = Solution()
- print(obj.countSubarrays(nums=[1, 3, 2, 3, 3], k=2)) # expect: 6
- print(obj.countSubarrays(nums=[1, 4, 2, 1], k=3)) # expect: 0
+ print(obj.countSubarrays(nums=[1, 3, 2, 3, 3], k=2))
+ print(obj.countSubarrays(nums=[1, 4, 2, 1], k=3))