Skip to content

3739. Count Subarrays With Majority Element II

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

Solutions

Solution 1: Binary Indexed Tree

According to the problem description, we can treat elements equal to \(\textit{target}\) in the array as \(1\), and elements not equal to \(\textit{target}\) as \(-1\). This way, \(\textit{target}\) being the majority element of a subarray is equivalent to the number of \(1\)s in the subarray being strictly greater than the number of \(-1\)s, i.e., the sum of the subarray is strictly greater than \(0\).

We can enumerate subarrays ending at each position. Let the prefix sum at the current position be \(\textit{s}\). Then the number of subarrays ending at this position with a sum greater than \(0\) is equivalent to the count of prefix sums that are less than \(\textit{s}\). We can use a Binary Indexed Tree to maintain the occurrence count of prefix sums, allowing us to efficiently calculate the answer. The range of prefix sums is \([-n, n]\). We can shift all prefix sums right by \(n+1\) units to transform the range to \([1, 2n+1]\).

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class BinaryIndexedTree:
    __slots__ = "n", "c"

    def __init__(self, n: int):
        self.n = n
        self.c = [0] * (n + 1)

    def update(self, x: int, delta: int) -> None:
        while x <= self.n:
            self.c[x] += delta
            x += x & -x

    def query(self, x: int) -> int:
        s = 0
        while x:
            s += self.c[x]
            x -= x & -x
        return s


class Solution:
    def countMajoritySubarrays(self, nums: List[int], target: int) -> int:
        n = len(nums)
        tree = BinaryIndexedTree(n * 2 + 1)
        s = n + 1
        tree.update(s, 1)
        ans = 0
        for x in nums:
            s += 1 if x == target else -1
            ans += tree.query(s - 1)
            tree.update(s, 1)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class BinaryIndexedTree {
    private int n;
    private int[] c;

    public BinaryIndexedTree(int n) {
        this.n = n;
        this.c = new int[n + 1];
    }

    public void update(int x, int delta) {
        for (; x <= n; x += x & -x) {
            c[x] += delta;
        }
    }

    public int query(int x) {
        int s = 0;
        for (; x > 0; x -= x & -x) {
            s += c[x];
        }
        return s;
    }
}

class Solution {
    public long countMajoritySubarrays(int[] nums, int target) {
        int n = nums.length;
        BinaryIndexedTree tree = new BinaryIndexedTree(2 * n + 1);
        int s = n + 1;
        tree.update(s, 1);
        long ans = 0;
        for (int x : nums) {
            s += x == target ? 1 : -1;
            ans += tree.query(s - 1);
            tree.update(s, 1);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class BinaryIndexedTree {
private:
    int n;
    vector<int> c;

public:
    BinaryIndexedTree(int n)
        : n(n)
        , c(n + 1, 0) {}

    void update(int x, int delta) {
        for (; x <= n; x += x & -x) {
            c[x] += delta;
        }
    }

    int query(int x) {
        int s = 0;
        for (; x > 0; x -= x & -x) {
            s += c[x];
        }
        return s;
    }
};

class Solution {
public:
    long long countMajoritySubarrays(vector<int>& nums, int target) {
        int n = nums.size();
        BinaryIndexedTree tree(2 * n + 1);
        int s = n + 1;
        tree.update(s, 1);
        long long ans = 0;
        for (int x : nums) {
            s += (x == target ? 1 : -1);
            ans += tree.query(s - 1);
            tree.update(s, 1);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
type BinaryIndexedTree struct {
    n int
    c []int
}

func NewBinaryIndexedTree(n int) *BinaryIndexedTree {
    return &BinaryIndexedTree{
        n: n,
        c: make([]int, n+1),
    }
}

func (t *BinaryIndexedTree) update(x, delta int) {
    for x <= t.n {
        t.c[x] += delta
        x += x & -x
    }
}

func (t *BinaryIndexedTree) query(x int) int {
    s := 0
    for x > 0 {
        s += t.c[x]
        x -= x & -x
    }
    return s
}

func countMajoritySubarrays(nums []int, target int) int64 {
    n := len(nums)
    tree := NewBinaryIndexedTree(2*n + 1)
    s := n + 1
    tree.update(s, 1)
    var ans int64
    for _, x := range nums {
        if x == target {
            s++
        } else {
            s--
        }
        ans += int64(tree.query(s - 1))
        tree.update(s, 1)
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class BinaryIndexedTree {
    private n: number;
    private c: number[];

    constructor(n: number) {
        this.n = n;
        this.c = Array(n + 1).fill(0);
    }

    update(x: number, delta: number): void {
        for (; x <= this.n; x += x & -x) {
            this.c[x] += delta;
        }
    }

    query(x: number): number {
        let s = 0;
        for (; x > 0; x -= x & -x) {
            s += this.c[x];
        }
        return s;
    }
}

function countMajoritySubarrays(nums: number[], target: number): number {
    const n = nums.length;
    const tree = new BinaryIndexedTree(2 * n + 1);
    let s = n + 1;
    tree.update(s, 1);
    let ans = 0;
    for (const x of nums) {
        s += x === target ? 1 : -1;
        ans += tree.query(s - 1);
        tree.update(s, 1);
    }
    return ans;
}

Comments