Skip to content

3737. Count Subarrays With Majority Element I

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

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