3737. Count Subarrays With Majority Element I

Array
Counting

TIME

O(n^2)

SPACE

O(1)

Intuition

A subarray is valid if target appears strictly more than half the time. With n ≤ 1000, checking all O(n²) subarrays is fast enough.

Approach

For each left boundary i, scan right and maintain a running count of how many times target appears. At each right boundary j:

length = j - i + 1
valid iff count * 2 > length

Incrementally extending the right boundary keeps each inner step O(1), so the total is O(n²).

Complexity

Time: O(n²)
Space: O(1)

Edge Cases

target not in nums → count stays 0 for all subarrays → return 0
All elements equal target → every subarray qualifies → n*(n+1)/2
Single-element subarray [target] → count=1, length=1, 2>1 ✓

Code

from typing import List


class Solution:
    def countSubarrays(self, nums: List[int], target: int) -> int:
        """
        3737. Count Subarrays With Majority Element I
        Time: O(n^2)
        Space: O(1)
        """
        n = len(nums)
        ans = 0
        for i in range(n):
            count = 0
            for j in range(i, n):
                if nums[j] == target:
                    count += 1
                if count * 2 > j - i + 1:
                    ans += 1
        return ans

/**
 * 3737. Count Subarrays With Majority Element I
 * Time: O(n^2)
 * Space: O(1)
 */
class Solution {
    public int countSubarrays(int[] nums, int target) {
        int n = nums.length, ans = 0;
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = i; j < n; j++) {
                if (nums[j] == target) count++;
                if (count * 2 > j - i + 1) ans++;
            }
        }
        return ans;
    }
}