611. Valid Triangle Number

Array Two Pointers Binary Search Sorting

Time: O(n²)

Space: O(1)

Intuition

Sort, then for each pair (i,j) with j fixed as the largest, find how many i satisfy nums[i]+nums[j-1]>nums[j] using binary search or two pointers.

Algorithm

1Sort the array.
2Fix the largest side c (index k from right): use two pointers l=0, r=k-1.
3If nums[l]+nums[r] > nums[k]: all pairs (l..r-1, r) work → count += r-l, r--. Else l++.

Common Pitfalls

•Triangle inequality only needs the two smaller sides to sum > largest side (since sorted, others are implied).

611.cs

// Approach: Sort, fix the largest side, then apply two pointers: when the
// two smaller sides sum exceeds the largest, all left-to-right pairs count.
// Time: O(n²) Space: O(1)

public class Solution
{
    public int TriangleNumber(int[] nums)
    {
        Array.Sort(nums);

        int arrayLength = nums.Length;
        int triangleCount = 0;

        for (int largestIndex = arrayLength - 1; largestIndex >= 2; largestIndex--)
        {
            int left = 0;
            int right = largestIndex - 1;

            while (left < right)
            {
                if (nums[left] + nums[right] > nums[largestIndex])
                {
                    triangleCount += right - left;
                    right--;
                }
                else
                {
                    left++;
                }
            }
        }

        return triangleCount;
    }
}

Was this solution helpful?