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 <= 1051 <= nums[i] <= 1091 <= target <= 109
Solutions
Too hard of a question for breakfast, doesn't really add much to yesterday's version.
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var countMajoritySubarrays = function(nums, target) {
const n = nums.length;
const dp = new Array(n * 2 + 1).fill(0);
dp[n] = 1;
let pos = n;
let sum = 0;
let res = 0;
for (let i = 0; i < n; i++) {
if (nums[i] === target) {
sum += dp[pos];
pos++;
} else {
pos--;
sum -= dp[pos];
}
dp[pos]++;
res += sum;
}
return res;
};