Why is this code failing a test case [Max Distance]

byMR

November 22, 2021

Problem: 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 -1.

Example :

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

INPUT:
9 8 7 -9 -1

EXPECTED OUTPUT:
1

MY OUTPUT:
0

The code I tried runs for all the cases except for the above given input, can anyone explain why is it failing that case and provide me with a rectified version?

My code(Python):

class Solution:
    def maximumGap(self, A):
        # write your method here
        m=-1
        for i in range(len(A)-1):
            j=len(A)-i-1
            if(A[i]<=A[j]):
                m=max(m,j-i)
        return m

I tried using 2 loops and it passes the above case but gives Time Limit Exceed for the other.

        m=-1
        for i in range(len(A)):
            for j in range(len(A)): 
                if(A[i]<=A[j]):
                    m=max(m,j-i)
        return m

>Solution :

You don’t need to test every pair. Search from the end until you find an element that’s >= the current element, that will be the biggest gap.

As an additional optimization, you can save the j value of that element, and break out of the outer loop when you get past it.

m = -1
maxj = len(A)
for i, el in enumerate(A):
    if i > maxj:
        break
    for j in range(len(A)-1, -1, -1):
        if el <= A[j]:
            m = max(m, j-i)
            maxj = j
            break