LeetCode Entry

3737. Count Subarrays With Majority Element I

25.06.2026 medium 2026 kotlin rust

Subarrays with majority element

3737. Count Subarrays With Majority Element I medium substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1401

Problem TLDR

Subarrays with majority element

Intuition

The problem space is small 1000, O(n^2) is accepted

Approach

• in the inner loop calculate a running sum

Complexity

• Time complexity: \(O(n^2)\)

• Space complexity: \(O(1)\)

Code

    fun countMajoritySubarrays(n: IntArray, t: Int) = n
    .indices.sumOf { i -> var c = 0
        (i downTo 0).count { j ->  if (n[j]==t) c++; c > (i-j+1)/2 }
    }

    pub fn count_majority_subarrays(n: Vec<i32>, t: i32) -> i32 {
        (0..n.len()).map(|i|{ let mut c = 0;
            (0..=i).rev().filter(|&j| {
                if n[j] == t { c += 1 }; c*2 > i-j+1
            }).count() as i32
        }).sum()
    }