Solution to Abs-Distinct by codility

29 Jan

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.

25 Replies to “Solution to Abs-Distinct by codility

  1. 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.

  2. 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.

  3. C# solution,

  4. C++

  5. Thanks for the website, have learnt a lot!

    Here is a O(n) time O(1) space Python solution. It’s slightly simpler and easier to reason than the code in your original post, but it’s basically the same thing.

  6. This is a simpler solution with 100 percent score::

  7. C# Code

    or

  8. This is my C++ version: https://app.codility.com/demo/results/trainingJ3QVPG-PGD/

    The single difference for the Sheng’s Python version is that in C++ we must to deal with the overflow of INT_MIN.

Leave a Reply

Your email address will not be published. Required fields are marked *

Please put your code into a <pre>YOUR CODE</pre> section. Thanks and Happy Coding!