Question: https://codility.com/demo/take-sample-test/count_triangles

Question Name: Count-Triangles or CountTriangles

This problem is nearly the same as the exercise in presentation of lesson 13.

Update on May 24, 2014: Thanks to @Adam. Fix a bug, which lower the performance.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
def solution(A): n = len(A) result = 0 A.sort() for first in xrange(n-2): third = first + 2 for second in xrange(first+1, n-1): while third < n and A[first] + A[second] > A[third]: third += 1 result += third - second - 1 return result |

if the list is sorted why do we set third = 0 at every iteration of first? Shouldn’t we set third to first + 2? I think A[first] + A[second] will always > A[third] where third < first + 2.

Yes, you are right! That was a bug. I have updated it. Thanks!

Maybe third = first + 2 should be in the second loop, and changed to third = second + 1 ?

Sorry, we could not. It will make the time complexity to be O(N^3).

Three loops normally leads to O(n^3), right? Did I miss something here?

Haha, that’s the tricky point. It is O(N^2), because the variable “third” (the same as “second”) is moving O(N) for each “first”.

Hi Sheng, great solution. Thank you!

Could you please explain line 12? I can’t understand how “result” can capture the number of triangle triplets…

For each round, the triangles include:

first, second, second + 1

first, second, second + 2

….

first, second, third – 2

first, second, third -1

In the line :—

result += third – second – 1

why are you doing -1 ? what is the need for that ?

first is the first item for the triangles.

second is the the second item for the triangles.

All the elements between second (exclusive) and third (exclusive) could be the third item for the triangles.

third – second – 1 is the number of elements in the range (second, third), both excusive.

After the array is sorted, the index of a number is different from that in the unsorted array. In other words, three numbers may form a triangle but their index in the unsorted may not be in the increasing order. Can you explain this?

The order does not matter at all! It is a trick.

Or in other words, you could sort their index, and the result is what you want.

I have a longer version coz there is a binary search, which is supposed to be faster than linear scan. I can’t prove it’s O(N^2), although codility said so.

Update: Oops, there is a flaw. Codility test cases didn’t complain though.

The loop-i and loop-j lead to O(N^2).