DSA problem
Valid Triangle Number
Given an integer array nums, return the number of triplets chosen from the array that can form the sides of a triangle. Three positive lengths a, b, c form a triangle if and only if the sum of any two sides is strictly greater than the third side: a + b > c, a + c > b, and b + c > a.
The brute-force triple loop checks every unordered triple in O(n^3) time and tests all three inequalities. While correct, that does not scale beyond a few hundred elements.
A much faster approach starts by sorting the array. After sorting, if a ≤ b ≤ c, the other two triangle inequalities (a + c > b and b + c > a) hold automatically because c ≥ b and c ≥ a give a + c ≥ a + b > a ≥ 0. Only the inequality a + b > c needs to be checked. So we only need to count triples (i, j, c) with i < j < c such that nums[i] + nums[j] > nums[c].
Fix the largest element c and use two pointers i = 0, j = c - 1 to count valid pairs against that c. If nums[i] + nums[j] > nums[c], then every i' ∈ [i, j - 1] also satisfies the inequality (since the array is sorted), so add j - i to the count and move j down. Otherwise advance i. Each outer iteration scans O(n) pairs, giving total O(n^2) time and O(1) extra space beyond the sort.
Examples
nums = [2,2,3,4]3nums = [4,2,3,4]4nums = [0,1,1,1]1Constraints
- 3 <= nums.length <= 1000
- 0 <= nums[i] <= 1000
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.