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

  • Your indentation seems to be off. The method inside the class should not be on the same level as the class – Graipher Nov 25 '16 at 13:01
  • 1
    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 – JMat Nov 25 '16 at 16:19

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

  • 2
    Links can rot. Please include the main content in the body of your answer and provide the link for reference. – Dannnno Jul 18 at 14:02

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.