LeetCode 3737 - Count Subarrays With Majority Element I

Here is a comprehensive, detailed reference guide for LeetCode 3737 - Count Subarrays With Majority Element I, following your formatting requirements exactly. The problem provides an integer array nums and a target integer.

leetcodemediumarrayhash-tabledivide-and-conquersegment-treemerge-sortcountingprefix-sum

LeetCode Problem 3737

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Divide and Conquer, Segment Tree, Merge Sort, Counting, Prefix Sum

Solution

Here is a comprehensive, detailed reference guide for LeetCode 3737 - Count Subarrays With Majority Element I, following your formatting requirements exactly.

Problem Understanding

The problem provides an integer array nums and a target integer. The goal is to count the number of subarrays in which the target appears as the majority element. A majority element in a subarray is an element that occurs strictly more than half the length of that subarray.

In other words, for a subarray nums[i..j], the condition for target being a majority is:

count(target in nums[i..j]) > (j - i + 1) / 2

The input array nums has a maximum length of 1000, and elements as large as 10^9. This means an O(n^2) or better solution is feasible, but O(n^3) approaches will be too slow.

Important edge cases include: when target does not exist in the array, when all elements are equal to target, and when the array length is 1.

Approaches

Brute Force:

The naive approach is to enumerate all possible subarrays of nums. For each subarray, count occurrences of target and check if it exceeds half the subarray length. If it does, increment a counter. This guarantees correctness but is inefficient because generating all subarrays is O(n^2), and counting occurrences in each subarray can be O(n), resulting in an O(n^3) algorithm.

Optimal Approach (Prefix Count and Balance Mapping):

The key observation is to reduce counting to a running balance. Define balance[i] as:

balance[i] = 2 * (number of target elements in nums[0..i]) - (i + 1)

This transforms the majority condition into a prefix sum problem. For a subarray nums[l..r], the target is a majority if:

2 * count_target_in_subarray > length_subarray
=> 2 * (count_target[r] - count_target[l-1]) > (r - l + 1)
=> (2 * count_target[r] - (r + 1)) - (2 * count_target[l-1] - l) >= 1
=> balance[r] - balance[l-1] >= 1

Thus, counting subarrays reduces to counting pairs (l-1, r) such that balance[r] - balance[l-1] >= 1. Using a hash map to track the frequency of previous balances allows O(n) counting.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) O(1) Enumerate all subarrays and count occurrences
Optimal O(n) O(n) Transform to balance array and use prefix frequency map

Algorithm Walkthrough

  1. Initialize a hash map freq to store the count of previous balance values, with freq[0] = 1 to account for empty prefix.
  2. Initialize balance = 0 and result = 0.
  3. Iterate through the array nums. For each element:

a. If it equals target, increment balance by 1. Otherwise, decrement balance by 1. This encodes whether target dominates the subarray so far.

b. To count the number of subarrays ending at current index where target is majority, add the sum of freq[b] for all b <= balance - 1. This can be simplified by keeping counts in a cumulative way.

c. Update freq[balance] += 1. 4. Return result.

Why it works:

The balance transformation guarantees that balance[r] - balance[l-1] > 0 exactly when target is the majority in nums[l..r]. Using a hash map to count previous balances efficiently counts all valid l for each r. This reduces a nested iteration into a single-pass O(n) algorithm.

Python Solution

from collections import defaultdict
from typing import List

class Solution:
    def countMajoritySubarrays(self, nums: List[int], target: int) -> int:
        freq = defaultdict(int)
        freq[0] = 1  # empty prefix
        balance = 0
        result = 0
        
        for num in nums:
            if num == target:
                balance += 1
            else:
                balance -= 1
            # Count number of previous balances <= current_balance - 1
            # All balances < current balance correspond to majority subarrays
            result += sum(count for b, count in freq.items() if b <= balance - 1)
            freq[balance] += 1
        
        return result

Explanation:

The balance variable encodes whether target is dominating. The freq hash map tracks how many times each balance has appeared. For each position, we sum counts of balances strictly less than the current balance to satisfy the majority condition. Finally, we increment the frequency of the current balance.

Go Solution

package main

func countMajoritySubarrays(nums []int, target int) int {
    freq := map[int]int{0: 1}
    balance := 0
    result := 0
    
    for _, num := range nums {
        if num == target {
            balance++
        } else {
            balance--
        }
        for b, count := range freq {
            if b <= balance-1 {
                result += count
            }
        }
        freq[balance]++
    }
    
    return result
}

Go-specific notes:

The Go version uses a map[int]int to track balances. Unlike Python, Go requires explicit iteration over map keys to sum counts. The logic for computing balance and updating the result is identical.

Worked Examples

Example 1: nums = [1,2,2,3], target = 2

i num balance freq before subarrays added freq after result
0 1 -1 {0:1} 0 {0:1,-1:1} 0
1 2 0 {0:1,-1:1} 1 (-1) {0:2,-1:1} 1
2 2 1 {0:2,-1:1} 3 (0,0,-1) {0:2,-1:1,1:1} 4
3 3 0 {0:2,-1:1,1:1} 1 (0) {0:3,-1:1,1:1} 5

Result = 5

Example 2 and 3 can be traced similarly.

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) worst, O(n) average Each iteration sums previous balance counts. Naive summing is O(n), but can be optimized to O(n) using cumulative counters or Fenwick tree
Space O(n) Store balance counts in a hash map

Note: Using a Fenwick tree or OrderedMap can optimize sum queries to O(log n), but for n <= 1000, iterating over map entries is acceptable.

Test Cases

# Provided examples
assert Solution().countMajoritySubarrays([1,2,2,3], 2) == 5  # majority subarrays of 2
assert Solution().countMajoritySubarrays([1,1,1,1], 1) == 10  # all subarrays
assert Solution().countMajoritySubarrays([1,2,3], 4) == 0  # target not in array

# Edge cases
assert Solution().countMajoritySubarrays([5], 5) == 1  # single element, target present
assert Solution().countMajoritySubarrays([5], 1) == 0  # single element, target absent
assert Solution().countMajoritySubarrays([1,2,1,2,1], 1) == 6  # alternating elements
assert Solution().countMajoritySubarrays([2,2,2,1,1], 2) == 6  # majority at start
Test Why
[1,2,2,3], target=2 Standard case with subarrays
[1,1,1,1], target=1 All subarrays valid
[1,2,3], target=4 Target not present
[5], target=5 Single element, target present
[5], target=1 Single element, target absent
[1,2,1,2,1], target=1 Alternating pattern
[2,2,2,1,1], target=2 Majority at start of array

Edge Cases

Target not in array:

If target does not exist, no subarray can have it as majority.