3
\$\begingroup\$

I am solving questions on arrays from here.

Problem: You are given an array of N integers, A1, A2 ,…, AN. Return maximum value of:

f(i, j) for all 1 ≤ i, j ≤ N.

f(i, j) is defined as |A[i] - A[j]| + |i - j|, where |x| denotes absolute value of x.

Solution approach:

|A[i] - A[j]| + |i - j| gives us 4 cases:

Case1:|A[i] - A[j]| + |i - j| = -A[i]+ A[j] - i + j = -(A[i]+ i) + ( A[j] + j)
Case2:|A[i] - A[j]| + |i - j| = -A[i]+ A[j] + i - j = -(A[i] - i) + (A[j]-j)
Case3:|A[i] - A[j]| + |i - j| = A[i]- A[j] - i + j  = (A[i] - i) - (A[j] -j) 
Case4:|A[i] - A[j]| + |i - j| = A[i]- A[j] + i - j  = (A[i] + i) - (A[j] + j)

Cases 1 and 4 are equivalent and can be find as the difference between the max and min value of A[i]+i

Cases 2 and 3 are equivalent and can be find as the difference between the max and min value of A[i]-i

How can I perfect this code?

def max_abs_diff(array):
    """ returns sum of absolute difference of values and corresponding indices of an array"""
    max1=[]#array to store maximum values given by A[i] + i
    min1=[]#array to store minimum values given by A[i] + i
    max2=[]#array to store maximum values given by A[i] - i
    min2=[]#array to store minimum values given by A[i] - i

    for i, elem in enumerate(array):

        max1.append(elem + i)  
        min1.append(elem + i)
        max2.append(elem - i)
        min2.append(elem - i)

    return max(max(max1) - min(min1) , max(max2)-min(min2))

Test cases:

print max_abs_diff([2,2,2]) == (2)
print max_abs_diff([2,-2,2])== (5)
print max_abs_diff([-4,-2,-3,-4,-5]) == (6)
print max_abs_diff([-1]) == (0)
print max_abs_diff([-5, 1, -3, 7, -1, 2, 1, -6, 5]) == (18)
print max_abs_diff( [6, -3, -2, 7, -5, 2, 1, -7, 6]) == (20)
print max_abs_diff([-5, -2, -1, -4, -7]) == (8)
\$\endgroup\$
5
\$\begingroup\$

First of all, I want to say this is really well presented. It just looks neat, with docstrings and comments and such. If you really want to perfect it, check the Python conventions in PEP 8 and linked documents. For example,

An inline comment is a comment on the same line as a statement. Inline comments should be separated by at least two spaces from the statement. They should start with a # and a single space.

and

The docstring is a phrase ending in a period. It prescribes the function or method's effect as a command ("Do this", "Return that"), not as a description; e.g. don't write "Returns the pathname ...".


I also very much appreciate the case analysis that has gone into the code to define those four cases, and so to reduce the naively quadratic function to a linear one. (Refering back to comments, that case analysis would not be at all amiss in a comment just after the docstring explaining the internal logic of the function)

Because, per the code and your case analysis, max1 and min1 always contain the same data, you could make the code shorter and reduce its space requirements by only having one of those. (And likewise for max2 and min2) However, see the next section.


In terms of the code itself, I suggest getting rid of those arrays. If they are only filled so that you can reduce them to a single maximum or minimum value, you might as well just track the rolling maximum or minimum as you go. This definitely saves space and probably saves time.

I would name the rolling reductions max_sum and max_difference rather than max1 and max2.


In terms of testing examples, do look for pathological cases. One case that always deserves to be checked, although it's not always obvious what the behaviour should be, is the case of an empty list.


Finally, it is generally worth using Python 3 in preference to Python 2 for new code, and especially practice code.

\$\endgroup\$
  • \$\begingroup\$ Thanks for your review and thanks for the appreciation too. My system is not compatible with Python 3 bt soon i will upgrade. \$\endgroup\$ – Latika Agarwal May 12 '18 at 16:48
  • \$\begingroup\$ Can you explain what are pathological cases? \$\endgroup\$ – Latika Agarwal May 12 '18 at 16:48
  • \$\begingroup\$ Pathological cases are inputs that do weird things, even though for the overwhelming majority of inputs the algorithm works as expected. "Edge cases" might be more appropriate wording in a testing context. \$\endgroup\$ – Josiah May 12 '18 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.