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

Question Name: AbsDistinct

In the original requirement, expected worst-case space complexity is O(N). But actually, O(1) is enought.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
def solution(A): abs_distinct = 1 current = max(abs(A[0]), abs(A[-1])) index_head = 0 index_tail = len(A)-1 while index_head <= index_tail: # We travel the array from the greatest # absolute value to the smallest. former = abs(A[index_head]) if former == current: # Skip the heading elements, whose # absolute values are the same with # current recording one. index_head += 1 continue latter = abs(A[index_tail]) if latter == current: # Skip the tailing elements, whose # absolute values are the same with # current recording one. index_tail -= 1 continue # At this point, both the former and # latter has different absolute value # from current recorded one. if former >= latter: # The next greatest value is former current = former index_head += 1 else: # The next greatest value is latter current = latter index_tail -= 1 # Meet with a new absolute value abs_distinct += 1 return abs_distinct |

Strange, but this solution gives me 100% with O(N*log(N)) detected complexity (C# variant: https://codility.com/demo/results/demoBBF8PJ-MRN/). The Caterpillar approach is a bit faster than my previous super-compact solution with the use of a HashSet: https://codility.com/demo/results/demoNYE9BD-9ZK/ (O(N*log(N)) complexity too)

Thanks for sharing your solutions!

FYI: if hash table is permitted, one line in Python is enough:

return len(set([abs(item) for item in A]))

I love Pythonnnnn!!!

Scarface, Codility’s complexity detection is just trying to guess (I don’t know how, though) but Sheng’s solution is O(N).

I do not know the details neither. But the detection complexity is not very accurate, as I talked with the staffs in Codility.

Here’s a more pythonic solution: https://codility.com/demo/results/demoFZ6NPU-CB4/

Thanks for sharing!

It’s my C# solution (with checking arithmetic overflow) https://codility.com/demo/results/demoHD6J7S-YWT/

Thanks for sharing!

Pavel,

Your solution fails for input: [-2147483648, -2147483648]

Array A is sorted in non-decreasing order, i.e. not necessarily in increasing.

Thanks for figuring out!

Well not a solution according to what the lesson teaches but it does the job well and has not that many lines of code; https://codility.com/demo/results/trainingJMCVQ4-Q53/

You do not need to convert set to list to use len() function.

Correct me if I’m wrong but I think he converted to a set to only capture distinct elements

Yes. But before the convert and in the for loop, (s)he transfers all input to their absolute values.

In python, this is a one-liner:

https://codility.com/demo/results/trainingHTA3X8-WDA/

Hi, can someone please elaborate a bit more on the key idea behind Caterpillar method? I read the document from codility and can sort of understand that it normally requires using two indices. But I feel I don’t fully understand the key principle of this idea.

On LeetCode, there is one tag called Two Pointer; is the idea of two pointer the same as caterpillar method?

Thanks.