LeetCode 611 - Valid Triangle Number
Count the number of possible triangles | GeeksforGeeks
==> diffcult to understand.
For example, if the input array is {4, 6, 3, 7}, the output should be 3. There are three triangles possible {3, 4, 6}, {4, 6, 7} and {3, 6, 7}. Note that {3, 4, 7} is not a possible triangle.
Given an array of integers, we need to find out whether it is possible to construct at least one non-degenerate triangle using array values as its sides. In other words, we need to find out 3 such array indices which can become sides of a non-degenerate triangle.
Read full article from Count the number of possible triangles | GeeksforGeeks
Count the number of possible triangles | GeeksforGeeks
Given an unsorted array of positive integers. Find the number of triangles that can be formed with three different array elements as three sides of triangles. For a triangle to be possible from 3 values, the sum of any two values (or sides) must be greater than the third value (or third side).
O(N^2) Python Version: https://github.com/algorhythms/LintCode/blob/master/Triangle%20Count.py
public int triangleCount(int S[]) { if (S == null || S.length <= 2) { return 0; } Arrays.sort(S); int res = 0; for (int end = S.length - 1; end > 1; end--) { int start = 0, mid = end - 1; while (start < mid) { if (S[start] + S[mid] <= S[end]) { start++; } else { res += mid - start;//key point mid--; } } } return res; }For example, if the input array is {4, 6, 3, 7}, the output should be 3. There are three triangles possible {3, 4, 6}, {4, 6, 7} and {3, 6, 7}. Note that {3, 4, 7} is not a possible triangle.
1. Sort the array in non-decreasing order.
2. Initialize two pointers ‘i’ and ‘j’ to first and second elements respectively, and initialize count of triangles as 0.
3. Fix ‘i’ and ‘j’ and find the rightmost index ‘k’ (or largest ‘arr[k]‘) such that ‘arr[i] + arr[j] > arr[k]‘. The number of triangles that can be formed with ‘arr[i]‘ and ‘arr[j]‘ as two sides is ‘k – j’. Add ‘k – j’ to count of triangles.
Let us consider ‘arr[i]‘ as ‘a’, ‘arr[j]‘ as b and all elements between ‘arr[j+1]‘ and ‘arr[k]‘ as ‘c’. The above mentioned conditions (ii) and (iii) are satisfied because ‘arr[i] < arr[j] < arr[k]'. And we check for condition (i) when we pick 'k'
4. Increment ‘j’ to fix the second element again.
Note that in step 3, we can use the previous value of ‘k’. The reason is simple, if we know that the value of ‘arr[i] + arr[j-1]‘ is greater than ‘arr[k]‘, then we can say ‘arr[i] + arr[j]‘ will also be greater than ‘arr[k]‘, because the array is sorted in increasing order.
5. If ‘j’ has reached end, then increment ‘i’. Initialize ‘j’ as ‘i + 1′, ‘k’ as ‘i+2′ and repeat the steps 3 and 4
Time Complexity: O(n^2). The time complexity looks more because of 3 nested loops. If we take a closer look at the algorithm, we observe that k is initialized only once in the outermost loop. The innermost loop executes at most O(n) time for every iteration of outer most loop, because k starts from i+2 and goes upto n for all values of j. Therefore, the time complexity is O(n^2).
Time Complexity: O(n^2). The time complexity looks more because of 3 nested loops. If we take a closer look at the algorithm, we observe that k is initialized only once in the outermost loop. The innermost loop executes at most O(n) time for every iteration of outer most loop, because k starts from i+2 and goes upto n for all values of j. Therefore, the time complexity is O(n^2).
static int findNumberOfTriangles(int arr[]) { int n = arr.length; // Sort the array elements in non-decreasing order Arrays.sort(arr); // Initialize count of triangles int count = 0; // Fix the first element. We need to run till n-3 as // the other two elements are selected from arr[i+1...n-1] for (int i = 0; i < n-2; ++i) { // Initialize index of the rightmost third element int k = i + 2; // Fix the second element for (int j = i+1; j < n; ++j) { /* Find the rightmost element which is smaller than the sum of two fixed elements The important thing to note here is, we use the previous value of k. If value of arr[i] + arr[j-1] was greater than arr[k], then arr[i] + arr[j] must be greater than k, because the array is sorted. */ while (k < n && arr[i] + arr[j] > arr[k]) ++k; /* Total number of possible triangles that can be formed with the two fixed elements is k - j - 1. The two fixed elements are arr[i] and arr[j]. All elements between arr[j+1] to arr[k-1] can form a triangle with arr[i] and arr[j]. One is subtracted from k because k is incremented one extra in above while loop. k will always be greater than j. If j becomes equal to k, then above loop will increment k, because arr[k] + arr[i] is always/ greater than arr[k] */ count += k - j - 1; } } return count; }
http://www.geeksforgeeks.org/find-number-of-triangles-possible/
http://www.fgdsb.com/2015/01/12/valid-triangles/
Method 1 (Brute force)
The brute force method is to run three loops and keep track of the number of triangles possible so far. The three loops select three different values from array, the innermost loop checks for the triangle property ( the sum of any two sides must be greater than the value of third side).
The brute force method is to run three loops and keep track of the number of triangles possible so far. The three loops select three different values from array, the innermost loop checks for the triangle property ( the sum of any two sides must be greater than the value of third side).
Time Complexity: O(N^3) where N is the size of input array.
Source: http://stackoverflow.com/questions/8110538/total-number-of-possible-triangles-from-n-numbers
Three segments of lengths A, B, C form a triangle iff
A + B > CB + C > AA + C > B
e.g.
6, 4, 5 can form a triangle10, 2, 7 can’t
Given a list of segments lengths algorithm should find at least one triplet of segments that form a triangle (if any).
Method should return an array of either:
- 3 elements: segments that form a triangle (i.e. satisfy the condition above)
- empty array if there are no such segments
|
Could you return the number of all valid triangles? You can assume there’s no duplicates in the original array.
注意k是在第二个for循环外面初始化的，且最多执行到N-1，所以虽然是3重循环但是还是O(N^2)复杂度。
int valid_triangle_nums(vector<double> nums) {sort(nums.begin(), nums.end());int count = 0;for(int i = 0; i < (int)nums.size() - 2; ++i) {int k = i + 2;for (int j = i + 1; j < nums.size(); ++j) {while (k < nums.size() && nums[i] + nums[j] > nums[k])++k;count += k - j - 1;}}return count;}
Could you return all valid triangles? You can assume there’s no duplicates in the original array.
http://www.geeksforgeeks.org/possible-form-triangle-array-values/vector<vector<double>> valid_triangles(vector<double> nums) {vector<vector<double>> ret;sort(nums.begin(), nums.end());for(int i = 0; i < (int)nums.size() - 2; ++i) {int k = i + 2;for (int j = i + 1; j < nums.size(); ++j) {while (k < nums.size() && nums[i] + nums[j] > nums[k])++k;for(int c = 1; c < k-j; ++c)ret.push_back({nums[i], nums[j], nums[c+j]});}}return ret;}
Given an array of integers, we need to find out whether it is possible to construct at least one non-degenerate triangle using array values as its sides. In other words, we need to find out 3 such array indices which can become sides of a non-degenerate triangle.
A Simple Solution is to generate all triplets and for every triplet check if it forms a triangle or not by checking above three conditions.
An Efficient Solution is use sorting. First, we sort the array then we loop once and we will check three consecutive elements of this array if any triplet satisfies arr[i] + arr[i+1] > arr[i+2], then we will output that triplet as our final result.
Why checking only 3 consecutive elements will work instead of trying all possible triplets of sorted array?
Let we are at index i and 3 line segments are arr[i], arr[i + 1] and arr[i + 2] with relation arr[i] < arr[i+1] < arr[i+2], If they can't form a non-degenerate triangle, Line segments of lengths arr[i-1], arr[i+1] and arr[i+2] or arr[i], arr[i+1] and arr[i+3] can't form a non-degenerate triangle also because sum of arr[i-1] and arr[i+1] will be even less than sum of arr[i] and arr[i+1] in first case and sum of arr[i] and arr[i+1] must be less than arr[i+3] in second case, So we don't need to try all the combinations, we will try just 3 consecutive indices of array in sorted form.
The total complexity of below solution is O(n log n)
Let we are at index i and 3 line segments are arr[i], arr[i + 1] and arr[i + 2] with relation arr[i] < arr[i+1] < arr[i+2], If they can't form a non-degenerate triangle, Line segments of lengths arr[i-1], arr[i+1] and arr[i+2] or arr[i], arr[i+1] and arr[i+3] can't form a non-degenerate triangle also because sum of arr[i-1] and arr[i+1] will be even less than sum of arr[i] and arr[i+1] in first case and sum of arr[i] and arr[i+1] must be less than arr[i+3] in second case, So we don't need to try all the combinations, we will try just 3 consecutive indices of array in sorted form.
The total complexity of below solution is O(n log n)
bool isPossibleTriangle(int arr[], int N){ // If number of elements are less than 3, // then no triangle is possible if (N < 3) return false; // first sort the array sort(arr, arr + N); // loop for all 3 consecutive triplets for (int i=0; i<N-2; i++) // If triplet satisfies triangle // condition, break if (arr[i] + arr[i+1] > arr[i+2]) return true;}