LeetCode Entry

3623. Count Number of Trapezoids I

02.12.2025 medium 2025 kotlin rust

Trapezoids count

3623. Count Number of Trapezoids I medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1191

Problem TLDR

Trapezoids count #medium

Intuition

    //         *              *          2
    //    *           *           *      3     2,3= 3
    //       *            *              2     2,2=1 + 2,3=3 = 4
    //             *                     1     skip
    //  *       *      *        *        4     2,4=6 + 3,4=(6+6+6)=18 + 2,4=6 = 6*5=30
    //     *       *     *       *       4     prev(30)+f(4,4)
    //        *       *      *           3     2*(3,2) + 3,3 + 2*(3,4)
    // 1 - 0
    // 2 - 1
    // 3 - 3
    // 4 - 6
    // 5 - 4+3+2+1=10 5*(5-1)/2       * * * * *
    // TLE? - yes, this is O(N^2), previous are too many
    // 35 minute, look for hints: they propose n^2 algo, there are too many groups
    //                            ugly math trick to solve this

Approach

• group by level Y
• each level count adds as c*(c-1)/2
• use previous levels sum

Complexity

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

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

Code

// 81ms
    fun countTrapezoids(p: Array<IntArray>) =
        p.groupingBy {it[1]}.eachCount().values.fold(0L to 0L){ (res,sum),c ->
        val ways = 1L*c*(c-1)/2; res + ways*sum to ways+sum }.first % 1000000007

// 63ms
    pub fn count_trapezoids(p: Vec<Vec<i32>>) -> i32 {
        (p.iter().map(|v| v[1]).counts().values().fold((0,0), |(r,s),&c|{
        let w = (c*(c-1)/2); (r+w*s,w+s) }).0 % 1000000007) as _
    }