Tutorial for Not a Triangle

The problem Not a Triangle asks us to find out the number of triplets from the given list that do not form a triangle. Let us revise a fundamental property - "Three numbers cannot form a triangle if the sum of any two is less than the third". Keeping this in mind, we can start building our solution.

Let us take a look at a naive solution. Consider all possible triplets and for each triplet check if the numbers are such that they do not form a triangle. Such a solution would work, but will it run within the time limit? Let us take a look at the time complexity of such a solution. It is of the order O(n^3). The value of 'n' can go up to 2000. So we are looking at more than 10^9 operations. This will not work in the given time period. So, we need to reduce the time complexity of our solution.

One thing we need to observe is that we don't need the actual triplets, we just need the number of triplets. In the solution described above, given 2 numbers, we need roughly 'n' comparisons in the worst case to find the number of values for which, having fixed the other two values, the sum of the two values selected is lesser than the third value we select. Now, if we are able to find such a value X for the selected 2 values such that X > sum_of_the_two_values, then any value greater than or equal to X will also satisfy the equation. So, our problem boils down to finding the lowest value X such that having selected 2 of the numbers, X > sum_of_the_two_values.

In such cases, sorting the values initially can help us. Let us sort the numbers that we take in for each test case. Now, having selected 2 of the numbers, we need to be able to find the number X in a complexity lower than O(n). As we can see, this is possible by using a technique called binary search. Consider that our array(A) of elements in sorted order is {10,20,30,40,50} and the 2 elements we have selected are 10 and 20. Now, we need to find the lowest number X such that X > 10+20. For this, we consider the interval of elements immediately after 20 till the end. In binary search, we make use of the fact that if a number T does not satisfy the given criteria, then either the numbers before T or the ones after T too will not satisfy the criteria. The technique is called binary search as at every stage, we maintain two values 'low' and 'high' which represent the interval that we are searching. We find the midpoint of this interval 'mid'=(low+high)/2. If the value at position 'mid' satisfies our criteria i.e. A[mid]>10+20, then there can be a lower value that satisfies the same criteria in the interval [low,mid]. So, we make the current value of 'mid' as the new value of 'high' and carry out the same procedure in the new interval. If we find that the new value at position 'mid' does not satisfy the criteria, then we can safely disregard all values below that value including it. This gives us our new interval as [mid+1,high]. Eventually, we will reach a state where the values of 'low' and 'high' are the same. This is when we have either found our required value X i.e. the lowest value such that X>sum_of_other_two_values or such a value does not exist in the array that we have.

Considering our array, let us see the values of low and high at every iteration. We start off with low=3 and high=5 which are the positions immediately after 20 and the last position respectively.

Now, we see that A[Mid] is 40 which is greater than 10+20. In the worst case, our answer can be 40, though there might be a chance that a better answer below 40 might be found. So, we change our interval to (Low, Mid), which is the same as changing the value of High to that of Mid. So in the second iteration, our values are:

We carry out integer division so (3+4)/2 = 3. Now 30 is not greater than 10+20. Thus, we can rest assured that we can't find the required number in the interval Low to Mid inclusive. So we need to search for an answer in the interval (Mid+1, High) which is the same as changing the value of Low to that of Mid+1. So in the next iteration our values change to :

We see that the values of Low and High are equal. So we have either found the required value X or such a value does not exist. We break out of the loop and make a final check to see if A[Mid] is greater than 10+20 and we see that it is. So, all numbers greater than and including the value at position Mid will not form a triangle with our selected numbers 10 and 20. This number is '2' and the numbers are 40 and 50. We add this to our final answer and continue finding other triplets.

Some care needs to be taken so that we don't consider the same triplet more than once. For this, selection of the two numbers needs to be done in such a way that the position of the second number being selected is always greater than the position of the first number. Also, the position of the third number is greater than that of the second number.

With a bit of preprocessing and usage of extra memory, it is possible to find the answer with a lower time complexity. We leave that as an exercise for the reader.