611. Valid Triangle Number
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:
Example 2:
Constraints:
- 1 <= nums.length <= 1000
- 0 <= nums[i] <= 1000
From: LeetCode
Link: 611. Valid Triangle Number
Solution:
Ideas:
1. Sorting: The array is sorted using qsort which is a standard library function in C for quicksort.
2. Three Pointers: Using a similar strategy as in Python:
- The outer loop iterates over each possible largest side.
- Two inner pointers (left and right) find pairs that can form a triangle with the current side (nums[i]).
3. Counting Triangles: For each valid configuration where the sum of two smaller sides is greater than the third side, count all possible valid combinations between left and right.
Code:
// Helper function to compare integers for qsort
int intCompare(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
// Function to count valid triangle triplets
int triangleNumber(int* nums, int numsSize) {
qsort(nums, numsSize, sizeof(int), intCompare); // Sort the array
int count = 0;
for (int i = 2; i < numsSize; i++) {
int left = 0, right = i - 1;
while (left < right) {
if (nums[left] + nums[right] > nums[i]) {
count += (right - left); // All pairs from left to right-1 with current right are valid
right--;
} else {
left++;
}
}
}
return count;
}