diff options
author | Jack Sangdahl <[email protected]> | 2025-04-28 18:48:09 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-04-28 18:48:09 -0600 |
commit | 2e8743f0ebda2c02358ce0f124a754fcf9059668 (patch) | |
tree | b337cd80935b671bccc697fab3a6222deb8abac6 | |
parent | c8dfd03864b524280c0c3c745e6a7c428b6bfe5b (diff) | |
download | leetcode-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.c | 20 | ||||
-rw-r--r-- | count_subarr_max_elem_k.py | 16 |
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)) |