why 2nd code is more faster than 1st one for the same question and 2nd having more statements in for loop?

Abhishek Kumar 0
Viewed 26

Time Limit Exceeded Your program took more time than expected. Expected Time Limit: 2.49sec

1st Code:

    subarr = []
    N = n+1 - k
    for i in range(N):
        S = arr[i:i+k]
        subarr.append(max(S))
    return subarr

2nd Code:

    l=[max(arr[:k])]

    for i in range(k,n):
        if l[-1]==arr[i-k]:
            l.append(max(arr[i-k+1:i+1]))
        elif l[-1]>arr[i]:
            l.append(l[-1])
        else:
            l.append(arr[i])
    return l
optimization python-3.x arrays
1 Answers

The second algorithm is smarter and does not call max on a newly created slice in every iteration. Creating a slice is a relative costly operation, so by avoiding it in some iterations, it will gain time.

You could express that second algorithm's loop in words like this:

  • If the previous subrange starts with the maximum value I identified for it, then that maximum will no longer be part of the current subrange, so I'll have to determine the new maximum by finding it using max.

  • Otherwise, that maximum will still be in the current subrange. If the current value that is going to be the newest member of the current range is less than that maximum, then the maximum will remain the same as I had for the previous range, so just copy it.

  • If however, the current value that is going to be part of the current range, is greater than the maximum I had, then forget about that previous maximum, and let this be the maximum for the current range.

The logic of the last two steps makes it possible to know the maximum of the current range without performing a slice+max operation.

trincot0
Related