trjhtr

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?

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)

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