You are given an array of N non-negative integers, A0, A1 ,…, AN-1. Considering each array element Ai as the edge length of some line segment, count the number of triangles which you can form using these array values.
Notes:
You can use any value only once while forming each triangle. Order of choosing the edge lengths doesn’t matter. Any triangle formed should have a positive area.
Return answer modulo 109 + 7.
For example,
A = [1, 1, 1, 2, 2]
Return: 4
Method1:
Assign first and second element first, find number of eligible third element.
Solution:
Time: O(n^2 logn)
Space: O(maxN)
public class Solution {
static class BIT {
int[] array;
public BIT(int n) {
this.array = new int[n + 1];
}
public void update(int i, int val) {
while (i < array.length) {
array[i] += val;
i += i & (-i);
}
}
public int sum(int i) {
if (i >= array.length) i = array.length - 1;
int sum = 0;
while (i > 0) {
sum += array[i];
i -= i & (-i);
}
return sum;
}
}
public int nTriang(ArrayList<Integer> A) {
if (A.size() <= 2) return 0;
Collections.sort(A);
BIT bit = new BIT(A.get(A.size() - 1));
for (int i = 0; i < A.size(); i ++) {
int curr = A.get(i);
bit.update(curr, 1);
}
long result = 0;
int i = 0;
while (i < A.size() - 1) {
int j = i + 1;
while (j < A.size()) {
int kSize = bit.sum(A.get(i) + A.get(j) - 1) - (j + 1);
result += kSize;
j ++;
}
i ++;
}
return (int) (result % 1000000007);
}
}
Method 2:
For each element, find the number of possible two other numbers that can form a triangle with it.
Time: O(n^2) Space: O(1)
public class Solution {
public int nTriang(ArrayList<Integer> A) {
if (A.size() <= 2) return 0;
Collections.sort(A);
long result = 0;
for (int i = 0; i < A.size(); i ++) {
int left = 0;
int right = i - 1;
while (left < right) {
if (A.get(left) + A.get(right) > A.get(i)) {
result += right - left;
right --;
} else {
left ++;
}
}
}
return (int) (result % 1000000007);
}
}