Find the index of the element with maximum absolute deviation

Question

I just completed a Codility test. The question presented was pretty simple but I may have over thought it.

Question:

Find the element which has the highest absolute deviation from the mean. E.g. Array = [1,1,-1,1].The average is 0.5, so the absolute deviation for each element in the array is [0.5,0.5,1.5,0.5] (note that the -1.5 goes to 1.5 after taking the absolute values of each deviation value) and thus the index with the max absolute deviation is 2 (the index starts from 0).

My code was:

def solution(A):
    if len(A) > 0:
        average = sum(A)*1.0/len(A)
        max_avg = 0
        pos = 0            
        for i in range(len(A)):
            if abs(A[i] - average) > max_avg:
                max_avg = abs(A[i] - average)
                pos = i
        return pos
    else:
        return -1

If there's a tie between the max deviation elements i.e. two or more indexes have the same absolute deviation then either of them can be given. The required time-complexity is \$O(N)\$ and space-complexity is \$O(1)\$. In theory, this problem should be really easy but this was my first technical test and I might have overlooked something. Did I possibly miss anything?

Answer 1

Note that in Python 3, you don't need * 1.0 to get floating-point division. On the other hand, in Python 2, range(len(A)) would use O(N) space.

I recommend three changes:

• Put the special case first, to reduce the separation between return -1 and the reason for returning -1.
• Rename max_avg → max_deviation.
• Use enumerate() to iterate over the array.

The revised solution would be:

def solution(A):
    if not A:
        return -1
    average = sum(A) * 1.0 / len(A)
    max_deviation = 0
    pos = 0
    for i, a in enumerate(A):
        if abs(a - average) > max_deviation:
            max_deviation = abs(a - average)
            pos = i
    return pos

Answer 2

@200_success already covered most of the points I had in my mind, apart from their suggestion one thing I would like to suggest you is that you can also use the built-in function max() with a custom key function for this.

The key function used with max is passed the item from the iterable, so we surely cannot use the sequence we are passing to our function because we need to find out the index. So, we can use range()(or xrange() in Python 2). Here I have defined the key_func inside of our function so that it can access average and seq.

def solution(seq):
    if not seq:
        return -1
    length = len(seq)
    average = sum(seq)/length

    def key_func(ind):
        val = seq[ind]
        return abs(average - val)

    pos = max(range(length), key=key_func)
    return pos

We can also move the key_func outside but in that case we need to make sure it knows about seq and average, to do that change key_func to accept three arguments. But as max can pass only one argument(i.e index) we need to specify the other two somehow, that's where functools.partial comes in:

from functools import partial


def find_abs(seq, average, ind):
    val = seq[ind]
    return abs(average - val)


def solution_range(seq):
    if not seq:
        return -1
    length = len(seq)
    average = sum(seq)/length
    # Create a new function around our key function using functools.partial
    # with seq and average.   
    key_func = partial(find_abs, seq, average)
    pos = max(range(length), key=key_func)
    return pos

Another option is to use enumerate with max instead of range(or xrange()), this will allow us to return both the index as well as corresponding item and now we need to pass only average to functools.partial:

def find_abs(average, index_val):
    index, val = index_val
    return abs(average - val)


def solution_enumerate(seq):
    if not seq:
        return -1
    length = len(seq)
    average = sum(seq)/length
    key_func = partial(find_abs, average)
    pos, item = max(enumerate(seq), key=key_func)
    return pos

---

For Python 2:

• To make sure the above solution work in Python 2 both fast and correctly use xrange() instead of range() and replace sum(seq)/length with sum(seq)/float(length).

• Python 2 also allowed argument tuple parameter unpacking but that is not available in Python 3 anymore, with the enumerate version we could have used it like this:

def find_abs(average, (index, val)):
    return abs(average - val)

Answer 3

if len(A) > 0 should be if A.

You should name thing better; A is both the wrong case and far too short.

You should short-ciruit the error case. In fact, you should throw an error.

If you're on Python 3, you don't need to * 1.0, and if not you should just from __future__ import division to get Python 3's behaviour. If you really don't want to, you should still use a float call instead.

You should use statistics.mean to find the mean. If you're on Python 2, this isn't an option without a backport. This will throw a good error for you, so you could remove that check.

You should use for i, val in enumerate(items) over for i in range(len(items)): val = item.

Since you only want the index, you can just do

deviations = (abs(item - average) for item in items)

and find the maximum of that. To get the index, just do

maxima, index = max((val, idx) for idx, val in enumerate(deviations))

Altogether:

import statistics

def solution(items):
    average = statistics.mean(items)

    deviations = (abs(item - average) for item in items)
    maxima, index = max((val, idx) for idx, val in enumerate(deviations))

    return index