Codility ‘AbsDistinct’ Solution

Short Problem Definition:

Compute number of distinct absolute values of sorted array elements.

Link

AbsDistinct

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N)

Execution:

Additional storage is allowed. Therefore a simple python solution will suffice.

Solution:
def solution(A):
    return len(set([abs(x) for x in A]))

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
  • Sean Janson

    Hi Martin,
    I originally came up with this classic hashset one-liner as well, but the fact that it sits in the ‘Caterpillar’ section got me thinking about more caterpillar-like solution.
    I sweated out a 2 pointer solution running against each other, seen [here]( https://codility.com/demo/results/trainingYZGW4U-7YF/ ). Not pure ‘caterpillar’, but it should run faster, especially in C/C++ environment.
    Any opinions?

    • I usually look at the time/space constraints and think of solutions that match these. Space O(n) – I am happy with a hash set 😉

      You are right, your solutions is a logical step if you think of caterpillars. Are there duplicate values? Maybe they meant the option of fast-forwarding duplicate values…? Or caterpillar equals two pointers ;)?

      I like your solution 🙂 It must be faster by a constant factor. Should you find any improvements to my other posts, let me know.