Skip to content

3737. Count Subarrays With Majority Element I

SourceBiweekly Contest 169 Q2DifficultyMediumRating1422

Description

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.

 

Example 1:

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

Output: 5

Explanation:

Valid subarrays with target = 2 as the majority element:

  • nums[1..1] = [2]
  • nums[2..2] = [2]
  • nums[1..2] = [2,2]
  • nums[0..2] = [1,2,2]
  • nums[1..3] = [2,2,3]

So there are 5 such subarrays.

Example 2:

Input: nums = [1,1,1,1], target = 1

Output: 10

Explanation:

​​​​​​​All 10 subarrays have 1 as the majority element.

Example 3:

Input: nums = [1,2,3], target = 4

Output: 0

Explanation:

target = 4 does not appear in nums at all. Therefore, there cannot be any subarray where 4 is the majority element. Hence the answer is 0.

 

Constraints:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 10​​​​​​​9
  • 1 <= target <= 109

Solutions

Solution 1: Enumeration

Thinking

A majority means \(\textit{target}\) occurs strictly more than half the length. The limits allow enumerating every subarray: fix the left end, scan right while counting \(\textit{target}\), and test \(2\cdot\textit{cnt}>\textit{len}\).

We can enumerate all subarrays and maintain a counter \(\textit{cnt}\) to record the number of times \(\textit{target}\) appears in the subarray, then determine whether \(\textit{target}\) is the majority element of that subarray.

Specifically, we enumerate the starting position \(i\) of the subarray in the range \([0, n-1]\), then enumerate the ending position \(j\) in the range \([i, n-1]\). For each subarray \(nums[i..j]\), we update the counter \(\textit{cnt}\). If \(\textit{cnt} \times 2 > j - i + 1\), it means \(\textit{target}\) is the majority element of this subarray, and we increment the answer by \(1\).

The time complexity is \(O(n^2)\), and the space complexity is \(O(1)\), where \(n\) is the length of the array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def countMajoritySubarrays(self, nums: List[int], target: int) -> int:
        n = len(nums)
        ans = 0
        for i in range(n):
            cnt = 0
            for j in range(i, n):
                cnt += int(nums[j] == target)
                if cnt * 2 > j - i + 1:
                    ans += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public int countMajoritySubarrays(int[] nums, int target) {
        int n = nums.length;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int cnt = 0;
            for (int j = i; j < n; ++j) {
                cnt += nums[j] == target ? 1 : 0;
                if (cnt * 2 > j - i + 1) {
                    ++ans;
                }
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int countMajoritySubarrays(vector<int>& nums, int target) {
        int n = nums.size();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int cnt = 0;
            for (int j = i; j < n; ++j) {
                cnt += nums[j] == target;
                if (cnt * 2 > j - i + 1) {
                    ++ans;
                }
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func countMajoritySubarrays(nums []int, target int) (ans int) {
    n := len(nums)
    for i := range nums {
        cnt := 0
        for j := i; j < n; j++ {
            if nums[j] == target {
                cnt++
            }
            if k := j - i + 1; cnt*2 > k {
                ans++
            }
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function countMajoritySubarrays(nums: number[], target: number): number {
    const n = nums.length;
    let ans = 0;
    for (let i = 0; i < n; ++i) {
        let cnt: number = 0;
        for (let j = i; j < n; ++j) {
            const k = j - i + 1;
            cnt += nums[j] == target ? 1 : 0;
            if (cnt * 2 > k) {
                ++ans;
            }
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
impl Solution {
    pub fn count_majority_subarrays(nums: Vec<i32>, target: i32) -> i32 {
        let n = nums.len();
        let mut ans = 0;

        for i in 0..n {
            let mut cnt = 0;
            for j in i..n {
                let k = (j - i + 1) as i32;
                if nums[j] == target {
                    cnt += 1;
                }
                if cnt * 2 > k {
                    ans += 1;
                }
            }
        }

        ans
    }
}

Comments