Lesson 4: Triangle (Triangle)

This is another math question.

First, let's sort the array in ascending order.

Then, we can have A[P] <= A[Q] <= A[R] for any 0 <= P < Q < R < N, as it is sorted in ascending order.

Then, assume all of these are positive values:
(0 <  A[P] <=  A[Q] <= A[R]).

Because the values are sorted, we can say as follows.
The condition 'A[P] < A[Q] + A[R]' always holds.
The condition 'A[Q] < A[P] + A[R]' also always holds, as 0 <= A[Q] <= A[R].

The condition 'A[R] < A[P] + A[Q]' needs to be checked., yet if we have a certain value R for A[R], we only have to check the two slots right before A[R], each of which as A[P] or A[Q] respectively, is bigger than A[R]. (We only have to if there is any triangular exist or not. as these two values are biggest, we only have to see these two.)

The reason why we can neglect any negative value is as follows.

If A[P] <= 0 <= A[Q] <= A[R], A[P] + A[Q] <= A[Q]. 
Then, it will be always `A[P] + A[Q] <= A[Q] <= A[R]', thus, 'A[R] < A[P] + A[Q]' is violated.

Thus, after sorting we only have check three consecutive slots from the head to the tail in the array A.


This strategy can give the score of 100%. While it would be better to use merge sort to guarantee the time complexity O(N log (N)), I used quick sort instead to simplify the implementation, since I don't think I need to bother myself to implement merge sort.

This question also requires us to avoid both overflow and underflow.

People often write like 'return *(int*)a - *(int*)b;' for the comparator function for C's qsort library function, this can cause underflow. Writing 'r < p + q' may cause overflow when p + q are large. These were good lessons for me...

int compare_int(const void *a, const void *b)
{
   //don't do 'return *(int*)a - *(int*)b;',
   //as this can cause underflow or overflow.

   if (*(int*)a == *(int*)b){
       return 0;
   }

   if (*(int*)a < *(int*)b){
       return -1;
   }
   
   return 1;
}

int solution(int A[], int N) 
{
    if (N < 3){
        return 0;
    }
    
    qsort(A, N, sizeof(int), compare_int);
    
    int i;
    for (i = 2; i < N; i++){
        
        int p = A[i - 2];
        int q = A[i - 1];
        int r = A[i];
        
        //neglect negative values.
        if (p <= 0){
            continue;
        }

        //if write like 'r < p + q', 'p + q' may overflow.
        if (r - p < q ){
            return 1;
        }
    }
    
    return 0;
}