Counting Valid Triangles: Why Reverse Traversal Matters

Problem Statement

Given an integer array, the task is to determine how many distinct triplets can serve as the three sides of a triangle. The triangle inequality requires that the sum of any two sides be greater than the third side (a + b > c).

Algorithmic Idea

The solution first sorts the array in ascending order. After sorting, it fixes the longest side c by iterating the array from the end toward the beginning (reverse traversal). For each fixed c, a two‑pointer scan is performed on the remaining prefix to find all pairs (a, b) that satisfy a + b > c.

Because the array is sorted, if nums[l] + nums[r] > nums[k] holds for a particular r, it also holds for every index between l and r. Therefore, the number of valid pairs for that r is r - l. After counting, r is decremented to test a smaller potential longest side. If the condition fails, l is incremented to increase the sum.

Complexity

Sorting costs O(n log n). The nested two‑pointer loops run in O(n^2) time in the worst case, and only constant extra space is used, yielding overall O(n^2) time and O(1) auxiliary space.

Complete Go Implementation

func triangleNumber(nums []int) int {
    // Rule for a triangle: a + b > c
    // 1. Sort the array in ascending order
    sort.Ints(nums)

    // 2. Iterate from the end (largest side) backwards
    res := 0
    for k := len(nums) - 1; k >= 2; k-- { // k is the index of the fixed longest side
        l, r := 0, k-1 // pointers for the remaining two sides
        for l < r {
            if nums[l] + nums[r] > nums[k] { // all elements between l and r also satisfy the rule
                res += r - l
                r-- // try a smaller r
            } else {
                l++ // increase l to make the sum larger
            }
        }
    }
    return res
}