leetcode

commit f0d62fda0a83822978791fd4294198515836e654
parent 0fc8d62c3689998b42af00464dbf7cd9c669cbb5
Author: Jack Sangdahl <jack@pngu.org>
Date:   Fri, 26 Jun 2026 09:06:57 -0600

3739. count subarrays with majority element 2

Diffstat:
A
count_subarr_majority_elem2.c
 | 
44
++++++++++++++++++++++++++++++++++++++++++++
A
count_subarr_majority_elem2.py
 | 
29
+++++++++++++++++++++++++++++

2 files changed, 73 insertions(+), 0 deletions(-)
diff --git a/count_subarr_majority_elem2.c b/count_subarr_majority_elem2.c
@@ -0,0 +1,44 @@
+// 3739. Count Subarrays With Majority Element II
+#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.
+ */
+
+long long countMajoritySubarrays(int *nums, int numsSize, int target) {
+  int balance = 0, shift = numsSize, smaller = 0;
+  long long ans = 0;
+  int *freq = (int *)calloc(numsSize * 2 + 1, sizeof(int));
+  freq[shift] = 1;
+  for (int i = 0; i < numsSize; i++) {
+    if (nums[i] == target) {
+      smaller += freq[balance + shift];
+      balance++;
+    } else {
+      balance--;
+      smaller -= freq[balance + shift];
+    }
+    ans += smaller;
+    freq[balance + shift]++;
+  }
+  free(freq);
+  return ans;
+}
+
+int main() {
+  int n1[] = {1, 2, 2, 3};
+  int n2[] = {1, 1, 1, 1};
+  int n3[] = {1, 2, 3};
+  long long r1 = countMajoritySubarrays(n1, ARRAY_SIZE(n1), 2);
+  long long r2 = countMajoritySubarrays(n2, ARRAY_SIZE(n2), 1);
+  long long r3 = countMajoritySubarrays(n3, ARRAY_SIZE(n3), 4);
+  printf("%lld\n", r1);
+  assert(r1 == 5);
+  printf("%lld\n", r2);
+  assert(r2 == 10);
+  printf("%lld\n", r3);
+  assert(r3 == 0);
+}
diff --git a/count_subarr_majority_elem2.py b/count_subarr_majority_elem2.py
@@ -0,0 +1,29 @@
+# 3739. Count Subarrays With Majority Element II
+from bisect import bisect_left
+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:
+        freq = [1 if i == target else -1 for i in nums]
+        pre, vis, ans = 0, [0], 0
+        for i in freq:
+            pre += i
+            idx = bisect_left(vis, pre)
+            ans += idx
+            vis.insert(idx, pre)
+        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))