aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--count_complete_subarr_arr.c50
-rw-r--r--count_complete_subarr_arr.py35
2 files changed, 85 insertions, 0 deletions
diff --git a/count_complete_subarr_arr.c b/count_complete_subarr_arr.c
new file mode 100644
index 0000000..bd16ad4
--- /dev/null
+++ b/count_complete_subarr_arr.c
@@ -0,0 +1,50 @@
+// 2799. Count Complete Subarrays in an Array
+#include "leetcode.h"
+
+/*
+ * you are given an array 'nums' consisting of positive integers. we call a
+ * subarray of an array complete if the following condition is satisfied. the
+ * number of distinct elements in the subarray is equal to the number of
+ * distinct elements in the whole array. return the number of complete
+ * subarrays. a subarray is a contiguous non-empty part of an array.
+ */
+
+int countCompleteSubarrays(int *nums, int numsSize) {
+ int elem[2001] = {0}, distinct = 0, ans = 0;
+ for (int i = 0; i < numsSize; i++) {
+ if (!elem[nums[i]])
+ distinct++;
+ elem[nums[i]]++;
+ }
+ int low = 0, high = 0, curr = 0;
+ memset(elem, 0, sizeof(elem));
+ while (curr < distinct) {
+ if (!elem[nums[high]])
+ curr++;
+ elem[nums[high]]++;
+ high++;
+ }
+ ans += numsSize - high + 1;
+ while (low < numsSize) {
+ elem[nums[low]]--;
+ if (!elem[nums[low]])
+ curr--;
+ while (high < numsSize && curr < distinct) {
+ if (!elem[nums[high]])
+ curr++;
+ elem[nums[high]]++;
+ high++;
+ }
+ if (curr < distinct)
+ break;
+ ans += numsSize - high + 1;
+ low++;
+ }
+ return ans;
+}
+
+int main() {
+ int n1[] = {1, 3, 1, 2, 2}, n2[] = {5, 5, 5, 5};
+ printf("%d\n", countCompleteSubarrays(n1, ARRAY_SIZE(n1))); // expect: 4
+ printf("%d\n", countCompleteSubarrays(n2, ARRAY_SIZE(n2))); // expect: 10
+}
diff --git a/count_complete_subarr_arr.py b/count_complete_subarr_arr.py
new file mode 100644
index 0000000..ca0371d
--- /dev/null
+++ b/count_complete_subarr_arr.py
@@ -0,0 +1,35 @@
+# 2799. Count Complete Subarrays in an Array
+from collections import Counter
+
+"""
+you are given an array 'nums' consisting of positive integers. we call a
+subarray of an array complete if the following condition is satisfied. the
+number of distinct elements in the subarray is equal to the number of
+distinct elements in the whole array. return the number of complete
+subarrays. a subarray is a contiguous non-empty part of an array.
+"""
+
+
+class Solution(object):
+ def countCompleteSubarrays(self, nums):
+ """
+ :type nums: List[int]
+ :rtype: int
+ """
+ n, k, i = len(nums), len(set(nums)), 0
+ ans, cnt = 0, Counter()
+ for j in range(n):
+ cnt[nums[j]] += 1
+ while len(cnt) == k:
+ cnt[nums[i]] -= 1
+ if cnt[nums[i]] == 0:
+ del cnt[nums[i]]
+ i += 1
+ ans += i
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.countCompleteSubarrays(nums=[1, 3, 1, 2, 2]))
+ print(obj.countCompleteSubarrays(nums=[5, 5, 5, 5]))