611. Valid Triangle Number

[mah-shamim]

Topics: Array, Two Pointers, Binary Search, Greedy, Sorting

Given an integer array nums, return the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

Example 1:

• Input: nums = [2,2,3,4]
• Output: 3
• Explanation: Valid combinations are:
  2,3,4 (using the first 2)
  2,3,4 (using the second 2)
  2,2,3

Example 2:

• Input: nums = [4,2,3,4]
• Output: 4

Constraints:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

[mah-shamim]

We need to find the number of triplets in an array that can form a triangle. The key property of a triangle is that the sum of any two sides must be greater than the third side.

Approach

1. Sort the Array: Sorting helps in efficiently checking the triangle condition. After sorting, we can fix the largest side and then check for pairs of smaller sides that satisfy the triangle inequality.
2. Two Pointers Technique: For each element as the potential largest side (starting from the end of the sorted array), use two pointers to find pairs of smaller sides such that their sum is greater than the largest side. If such a pair is found, all elements between the two pointers will also satisfy the condition (due to the sorted order), allowing us to count all valid triplets efficiently.

Let's implement this solution in PHP: 611. Valid Triangle Number

<?php
/**
 * @param Integer[] $nums
 * @return Integer
 */
function triangleNumber($nums) {
    sort($nums);
    $count = 0;
    $n = count($nums);
    for ($k = $n - 1; $k >= 2; $k--) {
        $i = 0;
        $j = $k - 1;
        while ($i < $j) {
            if ($nums[$i] + $nums[$j] > $nums[$k]) {
                $count += $j - $i;
                $j--;
            } else {
                $i++;
            }
        }
    }
    return $count;
}

// Test cases
// Example 1
$nums1 = [2, 2, 3, 4];
echo triangleNumber($nums1) . "\n"; // Output: 3

// Example 2
$nums2 = [4, 2, 3, 4];
echo triangleNumber($nums2) . "\n"; // Output: 4
?>

Explanation:

1. Sorting: The array is sorted first to facilitate the two-pointer technique.
2. Iterate from the End: Starting from the largest element (index k), we check pairs of elements from the start (index i) and just before k (index j).
3. Check Triangle Condition: If the sum of elements at i and j is greater than the element at k, then all elements between i and j-1 will also satisfy the condition with j and k. This allows us to add (j - i) to the count and decrement j to check the next smaller pair.
4. Adjust Pointers: If the sum is not greater, we increment i to consider a larger smallest element.

This approach efficiently narrows down the valid triplets by leveraging the sorted property and the two-pointer technique, ensuring an optimal solution with a time complexity of O(n²) due to the nested loops, which is efficient given the constraints.

[topugit]

Thanks for solving the problem of "Valid Triangle Number"

[mah-shamim]

Thanks