3739. Count Subarrays With Majority Element II

Description

You are given an integer array nums and an integer target.

Return the number of 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 <= 10​​​​​​​5
• 1 <= nums[i] <= 10​​​​​​​9
• 1 <= target <= 109

 

Solutions

Solution: Prefix Sum

• Time complexity: O(n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
const countMajoritySubarrays = function (nums, target) {
  const n = nums.length;
  const prefix = Array.from({ length: n * 2 + 1 }, () => 0);
  let balance = n;
  let preSum = 0;
  let result = 0;

  prefix[balance] = 1;

  for (const num of nums) {
    if (num === target) {
      preSum += prefix[balance];
      balance += 1;
    } else {
      preSum -= prefix[balance - 1];
      balance -= 1;
    }

    prefix[balance] += 1;
    result += preSum;
  }

  return result;
};