leetcode

commit 0fc8d62c3689998b42af00464dbf7cd9c669cbb5
parent 82839d5575c0ebe2897a1cd219067cbb3f701924
Author: Jack Sangdahl <jack@pngu.org>
Date:   Thu, 25 Jun 2026 09:42:13 -0600

3737. count subarrays with majority element 1

Diffstat:
A
count_subarr_majority_elem1.c
 | 
55
+++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
count_subarr_majority_elem1.py
 | 
35
+++++++++++++++++++++++++++++++++++

2 files changed, 90 insertions(+), 0 deletions(-)
diff --git a/count_subarr_majority_elem1.c b/count_subarr_majority_elem1.c
@@ -0,0 +1,55 @@
+// 3737. Count Subarrays With Majority Element I
+#include "leetcode.h"
+
+/*
+ * you are given an integer array 'nums' and an integer 'target'. return the
+ * number of subarrays of 'nums' in which 'target' is the majority element. the
+ * majority element of a subarray is the element that appears strictly more than
+ * half of the times in that subarray.
+ */
+
+int countMajoritySubarrays(int *nums, int numsSize, int target) {
+  int max = 0;
+  for (int i = 0; i < numsSize; i++) {
+    if (nums[i] != target)
+      nums[i] = 0;
+    else {
+      nums[i] = 1;
+      max++;
+    }
+  }
+  if (max <= 1)
+    return max;
+  int ans = max;
+  max = (max << 1) - 1;
+  int *pre = (int *)malloc((numsSize + 1) * sizeof(int));
+  pre[0] = 0;
+  for (int i = 0; i < numsSize; i++)
+    pre[i + 1] = pre[i] + nums[i];
+  for (int i = 2; i <= max; i++) {
+    int val = (i >> 1) + 1;
+    for (int j = 0; j + i <= numsSize; j++) {
+      int end = j + i;
+      int sum = pre[end] - pre[j];
+      if (sum >= val)
+        ans++;
+    }
+  }
+  free(pre);
+  return ans;
+}
+
+int main() {
+  int n1[] = {1, 2, 2, 3};
+  int n2[] = {1, 1, 1, 1};
+  int n3[] = {1, 2, 3};
+  int r1 = countMajoritySubarrays(n1, ARRAY_SIZE(n1), 2);
+  int r2 = countMajoritySubarrays(n2, ARRAY_SIZE(n2), 1);
+  int r3 = countMajoritySubarrays(n3, ARRAY_SIZE(n3), 4);
+  printf("%d\n", r1);
+  assert(r1 == 5);
+  printf("%d\n", r2);
+  assert(r2 == 10);
+  printf("%d\n", r3);
+  assert(r3 == 0);
+}
diff --git a/count_subarr_majority_elem1.py b/count_subarr_majority_elem1.py
@@ -0,0 +1,35 @@
+# 3737. Count Subarrays With Majority Element I
+from typing import List
+
+"""
+you are given an integer array 'nums' and an integer 'target'. return the
+number of subarrays of 'nums' in which 'target' is the majority element. the
+majority element of a subarray is the element that appears strictly more than
+half of the times in that subarray.
+"""
+
+
+class Solution:
+    def countMajoritySubarrays(self, nums: List[int], target: int) -> int:
+        n = len(nums)
+        pre = [0] * (2 * n + 1)
+        pre[n] = 1
+        cnt, pre_sum, ans = n, 0, 0
+        for i in nums:
+            if i == target:
+                pre_sum += pre[cnt]
+                cnt += 1
+                pre[cnt] += 1
+            else:
+                cnt -= 1
+                pre_sum -= pre[cnt]
+                pre[cnt] += 1
+            ans += pre_sum
+        return ans
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.countMajoritySubarrays(nums=[1, 2, 2, 3], target=2))
+    print(obj.countMajoritySubarrays(nums=[1, 1, 1, 1], target=1))
+    print(obj.countMajoritySubarrays(nums=[1, 2, 3], target=4))