LeetCode //C - 611. Valid Triangle Number

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:

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

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24