Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

4075. Count Subarrays With Majority Element II

My accepted Python solution to LeetCode problem 4075, Count Subarrays With Majority Element II, running in 657ms.

  • Difficulty: Hard
  • Python
  • Runtime 657ms
  • Memory 30.9MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 657ms, memory 30.9MB, accepted 2026-01-01.

python
class Solution:
    def countMajoritySubarrays(self, nums: List[int], target: int) -> int:
        n = len(nums)
        # Transform: target -> 1, non-target -> -1
        # A subarray has target as majority if sum > 0
        arr = [1 if x == target else -1 for x in nums]
        
        # Use prefix sums: sum(i,j) = prefix[j+1] - prefix[i]
        # We want prefix[j+1] - prefix[i] > 0, i.e., prefix[j+1] > prefix[i]
        # Count pairs where prefix[j] > prefix[i] for j > i
        
        # Use coordinate compression and BIT/merge sort for counting inversions
        from sortedcontainers import SortedList
        
        prefix = 0
        result = 0
        # For each prefix sum, count how many previous prefix sums are smaller
        sl = SortedList([0])  # Initial prefix sum of 0 (before index 0)
        
        for num in arr:
            prefix += num
            # Count prefix values strictly less than current prefix
            result += sl.bisect_left(prefix)
            sl.add(prefix)
        
        return result

Source