LeetCode Entry

3583. Count Special Triplets

09.12.2025 medium 2025 kotlin rust

Count a[i]==a[j] 2==a[k] sum

3583. Count Special Triplets medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1198

Problem TLDR

Count a[i]==a[j]*2==a[k] #medium #prefix_sum

Intuition

    // 8 4 2 8 4
    //   *        look for all 8 left and right
    //

Count total frequency F. Count frequency so-far L. Add for each middle: L * (F - L)

Approach

• or a single pass solution from lee: count frequency so-far F, count pairs (2x,x) so-far C+=F[x], add each C[x/2]

Complexity

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

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

Code

// 176ms
    fun specialTriplets(n: IntArray) = {
        val f = LongArray(200002); val c = f.clone()
        n.sumOf { x -> val r = 1L*c[x/2]*(1 - x%2); c[x] += f[x*2]; f[x]++; r }
    }() % 1000000007

// 36ms
    pub fn special_triplets(n: Vec<i32>) -> i32 {
        let mut f = [0i32; 200002]; let mut c = f.clone();
        n.iter().fold(0, |r, &x|{ let x = x as usize;
            let rx = c[x>>1] * ((x&1)^1)as i32;
            c[x] = (c[x] + f[x<<1])%1000000007;
            f[x] += 1; (r + rx)%1000000007
        })
    }