LeetCode Entry

611. Valid Triangle Number

26.09.2025 medium 2025 kotlin rust

Count triangles can be made from numbers search sum

611. Valid Triangle Number medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1124

Problem TLDR

Count triangles can be made from numbers #medium #binary_search #two_sum

Intuition

Sort. Binary Search: for every pair of numbers a and b search for c in [b-a..b+a] Two Sum: same idea, but left border is always goes forward, so we can do increament instead of bs

Approach

• for the BinarySearch upper bound is already less than a+b, the range is [0..a]

Complexity

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

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

Code

// 113ms
    fun triangleNumber(n: IntArray): Int {
        n.sort()
        return (2..<n.size).sumOf { i ->
            (1..<i).sumOf { j ->
                var lo = 0; var hi = j-1
                while (lo <= hi) {
                    val m = (lo + hi) / 2
                    if (n[m] > n[i]-n[j]) hi = m - 1 else lo = m + 1
                }
                j - lo
            }
        }
    }

// 44ms
    fun triangleNumber(n: IntArray): Int {
        n.sort()
        return (2..<n.size).sumOf { i ->
            var l = 0; var r = i-1; var c = 0
            while (l < r) if (n[l] + n[r] > n[i]) c += r-- -l else ++l
            c
        }
    }

// 18ms
    pub fn triangle_number(mut n: Vec<i32>) -> i32 {
        n.sort_unstable();
        (2..n.len()).map(|i| {
            let (mut l, mut r, mut c) = (0, i-1, 0);
            while l < r { if n[l]+n[r] > n[i] { c += r-l; r-=1} else { l+=1}}
            c as i32
        }).sum()
    }