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.
Solution to Count-Triangles by codility
n = len(A)
result = 0
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
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).
Why is this not working? (by performance). Only difference is, that I call initiate c in the second loop… which actually makes more sense to me.
I cannot see your complete code, since you did not follow the instructions to post code~
As far as I can see from your incomplete code, your solution (basically brute force solution) has a higher complexity. Please refer to the lesson 13’s presentation for more details (the link is provided in the blog).
How can i know what time and space complexity does the question require? Till now all the codility examples i have solved
required less than O(N^2) time complexity. So i was trying to solve this question within O(NlogN) time complexity but couldn’t succeed.
Then i looked at your solution and your time complexity is O(N^2). If i knew this before working on the problem i would have found it
easier. So is there a way to find out what the complexities the question requires?
Sorry, I did not notice the complexities of the question in advance. Giving the expected complexity would be a good hint in interview.