A zero-indexed array A consisting of N integers is given. A triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N and:
- A[P] + A[Q] > A[R],
- A[Q] + A[R] > A[P],
- A[R] + A[P] > A[Q].
For example, consider array A such that:
A[0] = 10 A[1] = 2 A[2] = 5
A[3] = 1 A[4] = 8 A[5] = 20
Triplet (0, 2, 4) is triangular.
GOOD SOLUTION (93% score, time complexity O(N*log(N))
class Solution {
public int solution(int[] A) {
Array.Sort(A);
if (A.Length <3) return 0;
for (int i=0 ; i<A.Length-2 ; i++)
{ if (A[i] + A[i+1] > A[i+2] )
{return 1;
break;
}
}
return 0;
}
}
I made one mistake here which I realised only once all the test results were ran: I didn't account if the triplet is formed by 3 maxValue integers (C# will wraparound the result of the sum of two maxValues).
BETTER SOLUTION (100% score, time complexity O(N*log(N)))
class Solution {
public int solution(int[] A) {
Array.Sort(A);
if (A.Length <3) return 0;
for (int i=0 ; i<A.Length-2 ; i++)
{ if (A[i] + A[i+1] > A[i+2] )
{
return 1;
break;
}
if (A[i] == A[i+2] &&
A[i+2] == A[i+1] &&
A[i] == Int32.MaxValue)
{
return 1;
break;
}
}
return 0;
}
}
PR
