6
\$\begingroup\$

I am solving interview questions from here.

Problem : Given an array A of integers, find the maximum of j - i subjected to the constraint of A[i] <= A[j].

Example : A = [3 5 4 2] Output : 2 for the pair (3, 4)

Here is my solution:

def maximum_gap( A):
    """find maximum gap between index(j -i ) with  A[i] <= A[j]"""
    gap = 0
    A = list(map( list,enumerate(A))) # get list of [index,value]
    for item in A:
        item[0],item[1] = item[1], item[0] # swap index with value
    a = sorted(A)  # sort list A as per values

    max_index = a[0][1] # initialise max_index to first index in sorted list
    min_index = a[0][1] # initialise min_index to first index in sorted list

    for v,i in a:
        if i > max_index:  # if current > max_index, set max to current
            max_index = i
        if i < min_index:  # if current < min_index, set min to current
            min_index = i
            max_index = i  # reset max to current

        gap_new = max_index - min_index  # find the maximum gap
        if gap < gap_new:
            gap = gap_new

    return gap

Test cases:

print maximum_gap([-1,-1,2])  == 2
print maximum_gap([1,3,5,7,2,4,10])  ==  6
print maximum_gap([3,2,1]) == 0
print maximum_gap([3,2,1,4]) == 3
print maximum_gap([2,2,1,4,3])  == 4
print maximum_gap([ 0,1,2,3])  == 3
print maximum_gap([ 100,100,100,100,100])  == 4

How can I make this code better?

\$\endgroup\$
6
\$\begingroup\$

The documentation for itertools.accumulate notes that you can pass min as the second argument to get a running minimum. So the maximum gap can be computed like this:

from itertools import accumulate

def maximum_gap(A):
    "Return maximum j-i subject to A[i] <= A[j]."
    B = sorted(range(len(A)), key=A.__getitem__)
    return max(j - i for i, j in zip(accumulate(B, min), B))

As for the test cases, this kind of problem is suitable for random testing. That's because it's straightforward to write a test oracle, a function solving the problem that is clearly correct (but inefficient). Here we could write:

from itertools import product

def maximum_gap_slow(A):
    "Return maximum j-i subject to A[i] <= A[j]."
    return max(j - i for i, j in product(range(len(A)), repeat=2) if A[i] <= A[j])

Then we can generate random test cases and use the test oracle to check the result, for example using the unittest module:

from random import randrange
from unittest import TestCase

class TestMaximumGap(TestCase):
    def test_random(self):
        for n in range(1, 100):
            A = [randrange(n) for _ in range(n)]
            self.assertEqual(maximum_gap(A), maximum_gap_slow(A), A)
\$\endgroup\$
  • \$\begingroup\$ Thanks for the review. I am using Python 2.7 so i think i cant use itertools.accumulate but i will keep a note of it. Secondly i wanted to ask how does " B = sorted(range(len(A)), key=A.__getitem__)" works? \$\endgroup\$ – Latika Agarwal May 21 '18 at 16:23
  • 1
    \$\begingroup\$ @LatikaAgarwal: (1) The documentation for itertools.accumulate has a recipe for implementing it that ought to work in Python 2.7. (2) It would be a good exercise to try to figure it out. \$\endgroup\$ – Gareth Rees May 21 '18 at 16:27
6
\$\begingroup\$

The code looks pretty good. Here are a few suggestions to make it more Pythonic.

Use generator expressions to their fullest

The entirety of the initialization of a can be reduced from:

A = list(map(list, enumerate(A)))  # get list of [index,value]
for item in A:
    item[0], item[1] = item[1], item[0]  # swap index with value
a = sorted(A)  # sort list A as per values

for v, i in a:
    ....

To:

for v, i in sorted((v, i) for i, v in enumerate(A)):
    ....

Use Python's builtins:

Python has the max() function that will replace

gap_new = max_index - min_index  # find the maximum gap
if gap < gap_new:
    gap = gap_new

with:

gap = max(gap, max_index - min_index)

similarly:

if i > max_index:  # if current > max_index, set max to current
    max_index = i

can be just:

max_index = max(max_index, i)

pep8

The violations were very minor, by I recommend formatting your code in accordance with pep8. This is important when sharing code, as the consistent style makes it much easier for other programmers to read your code. There are various tools available to assist in making the code pep8 compliant. I use the PyCharm IDE which will show pep8 violations right in the editor.

Restructured Code:

def maximum_gap(A):
    """find maximum gap between index(j -i ) with  A[i] <= A[j]"""

    min_index = max_index = len(A)
    gap = 0

    for v, i in sorted((v, i) for i, v in enumerate(A)):
        if i < min_index:  # if current < min, set min & max to current
            min_index = max_index = i
        else:
            # if current > max, set max to current
            max_index = max(max_index, i)

        # find the maximum gap
        gap = max(gap, max_index - min_index)

    return gap


assert maximum_gap([-1, -1, 2]) == 2
assert maximum_gap([1, 3, 5, 7, 2, 4, 10]) == 6
assert maximum_gap([3, 2, 1]) == 0
assert maximum_gap([3, 2, 1, 4]) == 3
assert maximum_gap([2, 2, 1, 4, 3]) == 4
assert maximum_gap([0, 1, 2, 3]) == 3
assert maximum_gap([100, 100, 100, 100, 100]) == 4
\$\endgroup\$

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.