Gfrktyl

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 interviewbit 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?

Found on www.interviewbit.com

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).