Count the number of possible triangles
Problem Description
Given an array of integers, find the number of triangles that can be formed using three distinct elements of the array as the lengths of the sides. A triangle is valid if the sum of any two sides is greater than the third side.
Example:
- Input:
arr[] = [4, 6, 3, 7]
- Output:
3
- Explanation: The valid triangles are
[3, 4, 6]
,[4, 6, 7]
, and[3, 6, 7]
. Note that[3, 4, 7]
is not a valid triangle because3 + 4
is not greater than7
.
Solution Code
import java.util.Arrays;
class Solution {
// Function to count the number of possible triangles.
static int countTriangles(int arr[]) {
int n = arr.length;
Arrays.sort(arr); // Sort the array to make it easier to find valid triangles
int count = 0;
// Fix the third side and use two pointers to find valid pairs
for (int i = n - 1; i >= 2; i--) {
int left = 0;
int right = i - 1;
while (left < right) {
// If arr[left] + arr[right] > arr[i], then all elements between left and right
// can form a triangle with arr[right] and arr[i]
if (arr[left] + arr[right] > arr[i]) {
count += right - left;
right--;
} else {
left++;
}
}
}
return count;
}
}
Hint
- Sort the array first. Use a two-pointer approach to efficiently count valid triangles by fixing the largest side and checking for valid pairs of smaller sides.
Approach Name
Two-Pointer Technique with Sorting
Intuition
By sorting the array, we can fix the largest side of the triangle and use two pointers to find valid pairs of smaller sides. If the sum of the two smaller sides is greater than the largest side, then all elements between the two pointers can form valid triangles with the largest side.
Algorithm
- Sort the array in ascending order.
- Fix the largest side of the triangle (starting from the end of the array).
- Use two pointers (
left
andright
) to find valid pairs of smaller sides. - If
arr[left] + arr[right] > arr[i]
, then all elements betweenleft
andright
can form valid triangles witharr[right]
andarr[i]
. Increment the count byright - left
and move theright
pointer to the left. - If
arr[left] + arr[right] <= arr[i]
, move theleft
pointer to the right. - Repeat until all possible triangles are counted.
Test Input
4 6 3 7
Complexity Analysis
- Time Complexity: O(n²), where
n
is the number of elements in the array. Sorting takes O(n log n), and the two-pointer approach takes O(n²) in the worst case. - Space Complexity: O(1), as we are using a constant amount of extra space.
This solution efficiently counts the number of valid triangles using sorting and a two-pointer approach, ensuring optimal performance for the given constraints.