# Solution to Triangle by codility

21 Jan

Question Name: Triangle

Update: we need two parts to prove our solution.

On one hand, there is no false triangular. Since the array is sorted, we already know A[index] < = A[index+1] <= A[index+2], and all values are positive. A[index] <= A[index+2], so it must be true that A[index] < A[index+1] + A[index+2]. Similarly, A[index+1] < A[index] + A[index+2]. Finally, we ONLY need to check A[index]+A[index+1] > A[index+2] to confirm the existence of triangular.

On the other hand, there is no underreporting triangular. If the inequality can hold for three out-of-order elements, to say, A[index]+A[index+m] > A[index+n], where n>m>1. Again, because the array is sorted, we must have A[index] < = A[index+m-1] and A[index+m+1] <= A[index + n]. So A[index+m-1] +A[index+m] >= A[index]+A[index+m] > A[index+n] >= A[index+m+1]. After simplification, A[index+m-1] +A[index+m] > A[index+m+1]. In other words, if we have any inequality holding for out-of-order elements, we MUST have AT LEAST an inequality holding for three consecutive elements.

In addition, here is a Java solution.

### 78 Replies to “Solution to Triangle by codility”

1. meatcomputer says:

I have a misunderstanding with either your solution or the problem.
I tried this without sorting (assuming that I couldn’t, I almost-finished a DAC solution before the time ran out). It looks like your solution works, and all the rest of the inequalities hold as long as the encoded inequality holds. What I don’t understand is: wouldn’t a false triangular be possible, since after sorting, the inequality can hold for an out-of-order element, an index ordering that I assumed had to be preserved?

• Sheng says:

On one hand, there is no false triangular. Since the array is sorted, we already know A[index] < = A[index+1] <= A[index+2], and all values are positive. A[index] <= A[index+2], so it must be true that A[index] < A[index+1] + A[index+2]. Similarly, A[index+1] < A[index] + A[index+2]. Finally, we ONLY need to check A[index]+A[index+1] > A[index+2] to confirm the existence of triangular.
On the other hand, there is no underreporting triangular. If the inequality can hold for three out-of-order elements, to say, A[index]+A[index+m] > A[index+n], where n>m>1. Again, because the array is sorted, we must have A[index] < = A[index+m-1] and A[index+m+1] <= A[index + n]. So A[index+m-1] +A[index+m] >= A[index]+A[index+m] > A[index+n] >= A[index+m+1]. After simplification, A[index+m-1] +A[index+m] > A[index+m+1]. In other words, if we have any inequality holding for out-of-order elements, we MUST have AT LEAST an inequality holding for three consecutive elements.
Hope this helps!

• Sandeep says:

Hello,
Thanks for you answers. Here is what is confusing me
“Assume that:
N is an integer within the range [0..100,000];
each element of array A is an integer within the range [âˆ’2,147,483,648..2,147,483,647].

The elements in the array can be negative, but you insist they are positive. Am I missing something?

• Sheng says:

For the given definition of triangular, it is impossible to include a negative number in a triangular (If A < B < C < 0, A + B always < C.). My code did not assume all input are positive, but will skip all of negative numbers.

• Jim says:

Let put it this way.
1) sort the Array
2) to make a triangle:
2i) We set the longest side of the triangle . Let’s say it is A[i]
2ii) we need to find the two shorter sides that can add up to A[i], Obviously A[i-2], A[i-1 ] are the two biggest values that are left for choosing from. If A[i-2] + A[i-1] A[i] return true;

Now I get it!

2. VJKS says:

Hi, I used this java solution in Codility, which looks very much like your solution but I only got 81% and I don’t know why:

Any help would be appreciated. Thanks.

• Sheng says:

Because your posted code has some issue to show properly, I really do not know how to debug it. At least, it will fail in the overflow test. I appended a 100/100 Java solution in this post. Please refer it.

• Ivan says:

Do the sorting after the validation and cast to long everything in the sum.

• Sheng says:

Sorry, I didn’t catch your idea.

• ktoslepszy says:

I think this is becouse of intiger range:
there is a chance that : array[i] + array[i+1] > Integer.MAX_VALUE is true

• Michael Brown says:

‘array[i] + array[i+1] > array[i+2]’ was the route I initially took too for checking the triangle as that is the format they use in stating the question, but if you do the check this way you have to add overflow checking code such as:
if(A[i]>0&&A[i+1]>0&&A[i]+A[i+1]<0)return 1;
if(A[i+1]<0&&A[i+2]=0)return 0;
Even those overflow checks will only bring you to 93%.
Using ‘array[i] > array[i+2] – array[i+1]’ as Sheng does neatly eliminates the overflow error cases.

• michael brown says:

There was a mistype here and it’s not letting me edit:
if(A[i+1]<0&&A[i+2]=0)return 0; should be
if(A[i+1]<0&&A[i+2]=0)return 0;

3. Rob says:

>>Since the array is sorted, we already know A[index] < = A[index+1] A[index+n]
Can you explain that in more detail?
Thanks!

• Sheng says:

Sorry, it might be a bad description. We sort the array as the first step. So we are sure it is sorted in all the discussion.

I tried the follwoing code without sorting and it works. It has O(n) since there is no sorting included but th epage tells me that it has O(n*log(n)). Can you confirm this?

• Sheng says:

Codility.com can only estimate the complexity. Your solution is O(N).
I cannot find a counterexample for your solution. I cannot proof it neither. Sorry! If you find a solution, please do tell me. Thanks!

• Wei says:

Hi, I tried [2,4,5,10] using Behzad’s method. it is supposed to return 0, right? but the method will return 1. So this is a counter example right?

• Sheng says:

It is supposed to return 1, because there is a triangle [2, 4, 5].

• for the input [1, 1, 2, 3, 5] the solution returned a wrong answer (got 1 expected 0).

• Sheng says:

Thanks for providing a counter-example.

I’m not a serious programmer but I do it for the fun. But rather like the Math. I’ll look if I can find a proof for it.

• Sheng says:

Fun will turn you to be an expert programmer ðŸ™‚

6. Henrique says:

Hi,
It seems like the algorithm returns 1 for the array below, while it should return 0?
A = [10, 14, 5, 1]
I think it should return 0, because there’s no consecutive elements that satisfies the conditions given. What do you think?

• Sheng says:

Hi!
There is no requirement that, they need to be consecutive. And the [10. 14. 5] is a triangular.

• Henrique says:

In the first paragraph, they say: A zero-indexed array A consisting of N integers is given. A triplet (P, Q, R) is triangular if 0 â‰¤ P < Q < R < N

• Henrique says:

Oh, doh! I see where I failed, sorry!

• Sheng says:

That is fine. To err is human.
Enjoy coding!

7. Henrique says:

A zero-indexed array A consisting of N integers is given. A triplet (P, Q, R) is triangular if 0 â‰¤ P < Q < R < N
If this is the case, then the array [5, 2, 10, 1, 8] should not contains a triangular, because even though [5, 10, 8] is triangular, the P, Q and R indexes don't match the condition given above. Obviously, I'm wrong, because your solution results in 100% on codility, but I don't quite understand why… can you explain it in detail?
Thanks

• Sheng says:

Hello, you simply get lost in the index. The order of the index does NOT matter at all.
For your example, the P is 0, Q is 2, R is 4. That is it.

• Henrique says:

Right, P=0, Q=2 and R=4 in the original array, but you are sorting the array, that results in this new array: [1, 2, 5, 8, 10]. If you map the values of this new array to the indexes in the original array, you will have P=0, Q=4 and R=2, which does not follow the condition P < Q < R.
Well, we could just look at it differently and invert Q and R, making it Q=2 and R=4 so we could pass that condition. But if we do that, instead of checking A[P] + A[Q] > A[R], we would have to check for A[P] + A[R] > A[B], which would invalidate your algorithm.

• Henrique says:

It has been fun! The conclusion I came up with is that the indexes P, Q, R can be anything, but equal. That’s what they meant by 0 <= P < Q < R < N.
As for the sum condition, it still has to be A[P] + A[Q] > A[R], the reason being… that the array is sorted, so the other sums are pointless.
Just sharing my findings, HTH.

• Sheng says:

I am glad that you got the idea! It is tricky.

• This has been confusing me as well. I groaned when I realized P < Q < R only says they're not equal, since they're all interchangeable in the next part of the parameters.

8. Dan says:

One question: why are we allowed to sort the array ?

• Sheng says:

The question is: why cannot we sort it? There is no limitation on sorting. And sorting is good for the time complexity requirement.
In addition, three numbers are triangular if and only if:
A + B > C
A + C > B
B + C > A
(For simplification, we assume A, B, C are larger than 0.)
After sorting, with any three consecutive (non-decreasing) integers A, B, C, we already know:
A + C > B
B + C > A
Then, we only need to check A + B and C.
With negative or zero numbers, it is similar.

• Dan says:

Would it still be allowed to sort if the function should return the triangle positions A,B and C ?

• Sheng says:

Sure, it could sort in either case. If the function need to return the position index, you can build a struction to store both the index and the value(first is index, the second is the correponding value). For example, [0, 5], [1, 6], [2, 3], [3, 2] for input array [5, 6, 3, 2].
Then we can do the same process.
Finally, we return the index in the structures.

9. Karl says:

Hello,
In the question it states : 0 â‰¤ P < Q < R < N
In this scenario after sorting could we not have something that resembles :
[8 , 9 , 9 ,9 ,9 ,9]?
In this case by the inequality above a triangle does no exist, correct?

• Sheng says:

IMO, the triangles exist a lot. For example, (9, 9, 9) is a triangle.

• True, codility is wrong. They mention P+Q>R, but forget that P+Q>=R will also work.

• Sheng says:

How could they construct a triangle, if A[P] + A[Q] == A[R]? It’s impossible.

10. lei says:

i use the same method , but C++. why my code can’t be accepted. can you help me ?

• Sheng says:

Your posted code is incomplete due to the wordpress issue. It seems that your did not check the empty input and overflow when computing the sum.

11. Thomas says:

I don’t understand how extreme_empty(empty sequence) and extreme_single(single value) is expected to return 1. I return 0 for these test cases but it says it is wrong in C++ and should return 1.

• Sheng says:

I did not meet your problem. As far as I see, the “extreme_empty” and “extreme_single” are expected to return 0.

12. I’m glad I came here again to find simpler solutions, I’ll post mine even though I noticed reading the previous post that it’s doing some unnecessary work by comparing the other cases in my isTriangular method. I got 100% on codility:

13. C# 100, actually it is a copy of previous java version, all glory to Sheng

• Sheng says:

Thanks Kembl!

14. Mathieu says:

Hi, you don’t need to check the length of A. The simplified solution below works fine:

• Sheng says:

You are totally right! Thanks for sharing!

15. dwitee panda says:

c++ solution got 100%

16. Khurram Awan says:

Objective C solution

17. Someone says:

Good explanation, but there’s no need to check if len(A) < 3. Since you're iterating over xrange(A_len-2), any A_len that is smaller than 3 will become zero or negative when you subtract the 2. xrange(x) where x < 1 will be empty, i.e. not a single iteration will happen, and solution() will return 0.
By the way, note that you don't need the initial 0 in xrange(0, A_len-2) – it is the default, so xrange(A_len-2) is equivalent.

• Sheng says:

You are totally right. Thanks very much for your suggestions!

18. Dnait2 says:

What would you do if the array wasn’t sorted?
In the problem description I can’t find that assumption…
A zero-indexed array A consisting of N integers is given. A triplet (P, Q, R) is triangular if 0 â‰¤ P < Q < R 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.
Write a function:
class Solution { public int solution(int[] A); }
Even the example is unsorted, and sorting it, wouldn’t guarantee the condition:
0 â‰¤ P < Q < R < N
Which are indexes, not values..

• Sheng says:

That’s why I sorted the input array firstly.

19. laaptu says:

Hey Sheng,
First of all great site. After I find my own solution, I check your site for answers. I couldn’t understand this “In other words, if we have any inequality holding for out-of-order elements, we MUST have AT LEAST an inequality holding for three consecutive elements.” Do we need to check this as well?
Further, if we modify the question to find the all the triangles in a given array, then I believe we also need to check for out of order elements as well.

• Sheng says:

Hi Laaptu, thanks for visiting!
The whole paragraph before “In other words, …” is used to prove this statement. Because we ONLY need to check the existence, we do not need to check all combinations.
And you are right, if we are going to find all the triangles, we need to check all.

• laaptu says:

Awesome. Thanks

20. Manuel says:

javascript solution got 100%

21. Manuel says:

javascript solution 100%

22. Dimitri says:

Checking just the central elements is enough it seems.

• Sheng says:

The solution is apparently wrong. Please try [1, 1, 1, 1, 5, 5, 5].
PS: it’s totally by coincidence that your solution could pass the tests.

23. Rafael says:

Solution that works with negative numbers:

• Sheng says:

Please refer to the “Guideline for Comments” on the right column for posting code. Thanks!

24. Ramazan says:

– My solution is correct except that it runs int O(N^3) time.

25. isa says:

lol, I tried so hard implementing a good sorting algorithm, when apparently it is allowed to use A.sort(), I was a fool.

• Sheng says:

No, you were just practicing with a sorting algorithm ðŸ˜‰

26. Rilakkuma says:

Maybe I’m wrong, but I feel that the assume at the start is not correct. At first glance all the solutions are check neibouring values, but I’m now sure about about that, since the array can contain duplicates. For example values [1, 1, 1, 10, 10, 10, 12] does not having triangular:

1 + 10 > 12 failed
10 + 12 > 1 success
12 + 1 > 10 success

But your solution gives 1 as an answer since you’re checking the 10 + 10 > 12

UPDATE:
Iâ€™m not sure, but it seems that not all of your sugesssuins is right. Soring arrays is a good point? but doint forget it can contain duplacates so it is not enough just to check neigbouring elements. For example is you check array [1, 10, 12] it is not valid triangular:

1 + 10 > 12 failed
10 + 12 > 1 success
12 + 1 > 10 success

And you code will return 0. And that is correct. But if you check an array of [1, 1, 10, 10, 12] it will give 1 because you check 10 + 10 > 12!

• Sheng says:

I do not quite understand your concern. In input [1, 1, 10, 10, 12], [10, 10, 12] is actually a valid triangle, right?

In the problem description: A triplet (P, Q, R) is triangular if 0 â‰¤ P < Q < R < N and .... P, Q, R is some index, not the value. The A[P], A[Q], and A[R] can hold the same value.

• Fiaz says:

Hi Sheng,

In the same example [1, 1, 10, 10, 12], as per your statement [10, 10, 12] is valid.
Isn’t [1,10,10] also a valid triangle. Am i going in the wrong direction. Please explain.

• Sheng says:

[1,10,10] is a valid triangle.

The question is: returns 1 if there exists a triangular triplet for this array and returns 0 otherwise

If there are 1, or 2, or more triagnular, the code should return 1.

27. Neha Daga says:

sorry forgot to write my code in the tags.

Can you please explain what’s wrong with my code?

• Sheng says:

I am not familiar with Java. But at line #17, the index i-1 and i-2 might be negative, right?

28. 100% javascript solution

29. Ajeje says:

Hi all
thanks for this blog: it’s really amazing, encouraging and supporting !!! ðŸ˜€
1) <=0 side cannot belong to a triangle right ? (codility says "A triplet (P, Q, R) is triangular if 0 â‰¤ P < Q < R < N" I think it should be 0<P …) neither a triangle may have 2 or 3 equal sides
2) while I understand that the exercise only requests whether there is at least 1 triangle within the set of sides, I have compared all triangles extracted by the algorithm you shared with the ones extracted by a more exhaustive search and I find a number more: isn't this a potential underreporting ?

e.g. this few cases:
A: [1, 2, 5, 6, 7]
exhaustive: [2,5,6, 2,6,7, 5,6,7]
fast: [2,5,6, 5,6,7]

A: [1, 4, 5, 6, 8]
exhaustive: [4,5,6, 4,5,8, 4,6,8, 5,6,8]
fast: [4,5,6, 5,6,8]

• Sheng says:

You are very welcome!

RE: codility says “A triplet (P, Q, R) is triangular if 0 â‰¤ P < Q < R < N” I think it should be 0 < P â€¦
P, Q, R is the index, NOT the value. There is no restriction about the range of A[P] A[Q] or A[R].

RE: isn’t this a potential underreporting?
Yes, you are right. My algorithm does not find out ALL the triangular, but is enough to determine the triangular’s existence.