Is Count Subarrays With Majority Element II easy or hard?

The problem is classified as Hard because it requires transforming a majority condition into a prefix inequality and then counting valid ranges efficiently. Understanding Fenwick Trees or divide-and-conquer counting is usually necessary to reach the optimal solution.

Count Subarrays With Majority Element II Python/Java solution

Python, Java, C++, Go, and TypeScript implementations typically follow the same pattern: compute prefix sums, compress their values, and use a Fenwick Tree to query how many earlier prefixes are smaller. Each iteration updates the tree with the current prefix index.

How to solve Count Subarrays With Majority Element II in O(n log n)?

Transform the array into a prefix balance where the target element contributes +1 and all others contribute -1. A subarray has a majority when its prefix difference is positive. Use coordinate compression and a Binary Indexed Tree to count how many previous prefix sums are smaller than the current prefix while scanning the array.

What is the best approach for Count Subarrays With Majority Element II?

The most efficient method uses a prefix sum transformation combined with a Binary Indexed Tree (Fenwick Tree). Convert the majority condition into a prefix balance problem and count valid prefix pairs using Fenwick Tree queries. This reduces the complexity to O(n log n) with O(n) extra space.

Is Count Subarrays With Majority Element II asked at Google/Amazon/Meta?

Majority-element and prefix-sum counting problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving prefix sums, Fenwick Trees, or merge-sort counting are common in hard-level algorithm rounds.

What data structure is used in Count Subarrays With Majority Element II?

The key data structure is a Binary Indexed Tree (Fenwick Tree) used for efficient prefix frequency queries. The algorithm also relies on prefix sums and coordinate compression to handle negative or large prefix values.

What is the time complexity of Count Subarrays With Majority Element II?

The optimal solution runs in O(n log n) time using prefix sums and a Binary Indexed Tree to count valid prefix pairs. Simpler approaches such as checking every subarray take O(n^2) or O(n^3), which become too slow for large arrays.

Description Hints 5 Solution Video 1:00:05

3739. Count Subarrays With Majority Element II

Hard65.2% acceptance2 companies

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 <= 10⁵
1 <= nums[i] <= 10⁹
1 <= target <= 10⁹

Asked at 2 companies

Amazon Microsoft

Topics

Hints open one at a time

Hint 1

Convert to +1/-1: let arr[i] = 1 if nums[i] == target else -1.

Hint 2

Build prefix sums: pref[0]=0, pref[k] = pref[k - 1] + arr[k - 1] for k=1..n.

Hint 3

Count pairs (i < j) with pref[j] > pref[i] (these correspond to subarrays where target is majority).

Hint 4

Use coordinate compression on all pref values and a Fenwick tree / ordered map: iterate k from 0..n, query how many previous pref are < current, add to ans, then update.

Hint 5

If target never appears return 0.

1:00:05

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def countMajoritySubarrays(self, nums: List[int], target: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[1,2,2,3]
2

Input

[1,1,1,1]
1

Input

[1,2,3]
4

Your code is saved on this device.Solution