Valid Triangle Number

Problem statement

Given an integer array of side lengths, return how many triplets can form a non-degenerate triangle. Three lengths a ≤ b ≤ c work when a + b > c.

Example:

Input:

nums = [2, 2, 3, 4]

Expected output:

3

Why: the valid triplets are (2, 3, 4), (2, 3, 4), and (2, 2, 3).

Practice on LeetCode: Valid Triangle Number

Golang Solution

Sort ascending. Fix the largest side at index k, then two-pointer on the prefix: if nums[i] + nums[j] > nums[k], every index from i to j-1 also works with j and k, so add j - i and move j left; otherwise bump i.

Time: O(n²) after an O(n log n) sort
Space: O(1) extra beyond sorting

import "sort"

func triangleNumber(nums []int) int {
    sort.Ints(nums)

    count := 0
    n := len(nums)

    for k := n - 1; k >= 2; k-- {
        i := 0
        j := k - 1

        for i < j {
            if nums[i]+nums[j] > nums[k] {
                // All indices from i to j-1
                // can form a triangle with j and k.
                count += j - i
                j--
            } else {
                // nums[i] is too small.
                i++
            }
        }
    }

    return count
}