Find max in-order difference in array

Question

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

If there is no solution possible, return 0.

Example :

A : [3 5 4 2]

Output : 2 for the pair (3, 4)

My Code :

def maximumGap(self, A):
 if len(A)==1: return 0
 a_list = sorted(([Val,indeX] for indeX,Val in enumerate(A)), reverse=True)
 rest = [indeX for val,indeX in a_list] # rest stores all the index from a_list which is sorted in decreasing order
 len_rest = len(rest)
 del a_list[:]
 results = []
 
 for i in range(len_rest):
 if i != len_rest-1:
 results.append(rest[i] - min(rest[i+1:]))
 else: continue
 ans = max(results)
 if ans < 0: return 0
 else: return ans

Sample input taken for explanation:

A = [34, 8, 10, 3, 2, 80, 30, 33, 1]

Brief summary of my algorithm:

1. a_list is a list of lists which will store all the numbers from the orginal list (list A) in sorted order along with their indexes.

`a_list = [[80, 5], [34, 0], [33, 7], [30, 6], [10, 2], [8, 1], [3, 3], [2, 4], [1, 8]]`

2. rest is a list which will store all the indexes from a_list.

`rest = [5, 0, 7, 6, 2, 1, 3, 4, 8]`

(After this, a_list is deleted to empty the space)

3. Now, the crux of the logic is: Since list is sorted in descending order, I need not take care of the constraint: A[i] <= A[j]

I will just iterate the list: rest and in each iteration, say 0th iteration, rest[0] = 5 is subtracted from the smallest remaining elements in list: rest

Each result of the iteration is stored in list: results

4. results = [5, -1, 6, 5, 1, -2, -1, -4]

5. Max of list results will give me the answer.

(It is important to note that while sorting the list we must also store the original index of the values instead of blindly sorting it.)

Now, coming to the actual problem:

On submitting my solution at IinterviewBit website, my code is giving correct answers to all test cases but time limit is exceeded.

I am not able to figure out what how to optimise this further.

Time complexity of my code (correct me if I am wrong) is \$O(n \log n)\$.

Sorting takes \$O(n \log n)\$ time in the worst case when using sort function in Python.

My main question is how to optimise this code further?

• JMat: there is a solution in a o(N) complexity: see, you only have to keep track of the lowest value seen yet and compute the difference between the current point and the lowest value seen yet

Answer 1

Layout

Lines like this:

if len(A)==1: return 0

are customarily split across 2 lines:

if len(A)==1:
 return 0

The black program can be used to automatically reformat the code.

Long lines of code are hard to read:

rest = [indeX for val,indeX in a_list] # rest stores all the index from a_list which is sorted in decreasing order

The comment can be moved above the line of code:

# rest stores all the index from a_list which is sorted in decreasing order
rest = [indeX for val, indeX in a_list]

Simpler

Consider deleting this line:

del a_list[:]

These lines can be deleted since they are not needed:

else:
 continue

This check in the for loop is not needed:

if i != len_rest-1:

if len_rest is set like this:

len_rest = len(rest) - 1

This could make the code more efficient since the check is not executed every time through the loop.

There is no need for the ans variable or its checking code. The answer can be directly returned, as you will see below.

Documentation

The PEP 8 style guide recommends adding docstrings for functions.

Naming

PEP 8 recommends snake_case for function and variable names.

maximumGap would be maximum_gap

A is not a very meaningful name for a variable. integers is more appropriate.

---

Here is new code with some of the suggestions above:

def maximum_gap(integers):
 if len(integers) == 1:
 return 0
 a_list = sorted(([Val, index] for index, Val in enumerate(integers)), reverse=True)
 # rest stores all the index from a_list which is sorted in decreasing order
 rest = [index for val, index in a_list]
 len_rest = len(rest) - 1
 results = [0]
 for i in range(len_rest):
 results.append(rest[i] - min(rest[i + 1 :]))
 return max(results)
print(maximum_gap([3, 5, 4, 2]))
print(maximum_gap([34, 8, 10, 3, 2, 80, 30, 33, 1]))

Answer 2

Actually in the last part, during the iteration over list named rest, its O(N^2), so, its not working. Refer to Geeksforgeeks for O(n).

• Dan Oberlam: Links can rot. Please include the main content in the body of your answer and provide the link for reference.