Optimising Performance of Codility Flags Python-CodePudding

I've written the below algorithm as a solution to Codility Flags. This passes the correctness checks, however it times out on most of the performance checks.

The complexity of this should be O(m**2) where m is the number of peaks in A and n is the length of A. However, the while potentialK > maxFlags loop should only execute until a suitable number of flags is found which satisfies the criteria. I'm not sure how to further optimise this for time complexity.

def solution(A):
    peaks = []
    distances = []
    if len(A) == 1: return 0
    for i in range(1, len(A) -1): 
        if A[i] > A[i-1] and A[i] > A[i 1]:
            if len(distances) == 0: 
                distances.append(i)
            else: 
                distances.append(i - peaks[-1]) 
            peaks.append(i)
    if len(peaks) == 0: return 0
    if len(peaks) == 1: return 1
    if len(peaks) == 2: return 2 if peaks[1] - peaks[0] >= 2 else 1
    potentialK = len(peaks)    
    maxFlags = 0 
    while potentialK > maxFlags: 
        cumDistance = 0 
        flags = 0
        firstFlag = True
        for i in range(1, len(distances)):
            cumDistance  = distances[i]
            if cumDistance >= potentialK: 
                if firstFlag: 
                    flags  = 2 
                    firstFlag = False
                else: 
                    flags  = 1
                cumDistance = 0
        if flags > maxFlags and flags == potentialK: 
            return flags 
        elif flags > maxFlags and potentialK > flags: 
            maxFlags = flags
        potentialK -= 1
    return maxFlags

CodePudding user response：

Your algorithm is O(n^2), since there can be O(n) peaks in the input. Speeding up your algorithm relies on the fact that you know the input size in advance.

Observe that the answer is an integer in the interval [1, ceil(sqrt(n))]. Any distance requirement that's less than 1 means that you can't place any flags. You can't place more than ceil(sqrt(n)) flags because of the distance requirement, even if every element was somehow a peak (which isn't possible).

So one optimization you could make is that you need to only check for O(sqrt(n)) potentialK values. (You posted this as an answer to your own question.) That would bring the runtime down to O(n^(3/2)), since m is O(n), which is apparently fast enough to pass Codility's tests, but I think that the runtime can still be improved (and so can the correctness).

We can make one more observation:

There exists a positive integer i such that:

for every j, such that j is a positive integer less than i, we can place j flags that are at least j distance apart
for every j, such that j is a positive integer greater than i, we cannot place j flags that are at least j distance apart.

This enables us to use binary search:

import math

def does_distance_work(peaks, distance):
    peak_count = 1
    last_peak = peaks[0]
    for i in range(len(peaks)):
        if peaks[i] >= last_peak   distance:
            peak_count  = 1
            last_peak = peaks[i]
        
    return peak_count >= distance


def solution(A):
    # Get the indices of the peaks.
    peaks = []
    for i in range(1, len(A) - 1):
        if A[i] > A[i - 1] and A[i] > A[i   1]:
            peaks.append(i)
    
    # Return 0 if no peaks.
    if not peaks:
        return 0
    
    # Check maximum value.
    if does_distance_work(peaks, math.ceil(math.sqrt(len(A)))):
        return math.ceil(math.sqrt(len(A)))

    # If neither of the above two checks apply, find the largest i (as specified above) using binary search.
    low, high = 1, math.ceil(math.sqrt(len(A))) - 1
    while low <= high:
        mid = low   (high - low) // 2
        mid_valid_distance = does_distance_work(peaks, mid)
        mid_plus_one_valid_distance = does_distance_work(peaks, mid   1)
        if not mid_valid_distance:
            high = mid
        elif mid_plus_one_valid_distance:
            low = mid   1
        else:
            return mid
    
    # If we've reached this line, something has gone wrong.
    return -1

which recurses to a depth of O(log(sqrt(n)), with O(n) work for each iteration of our binary search. Then the final runtime is O(n * log(sqrt(n))), which should (and does) pass the performance tests.

CodePudding user response：

I managed to optimize it as follows:

Since the distance between the individual flags has to be >= the number of flags, we know the maximum number of flags will be the root of the last element of peaks - the first element of peaks: sqrt(peaks[-1] - peaks[0])

I was then able to update the initial value of potentialK to

potentialK = math.ceil(math.sqrt(peaks[-1] - peaks[0]))

which should substantially reduce the number of iterations of the outer while loop.

import math 

def solution(A):
    peaks = []
    distances = []
    if len(A) == 1: return 0
    for i in range(1, len(A) -1): 
        if A[i] > A[i-1] and A[i] > A[i 1]:
            if len(distances) == 0: 
                distances.append(i)
            else: 
                distances.append(i - peaks[-1]) 
            peaks.append(i)
    if len(peaks) == 0: return 0
    if len(peaks) == 1: return 1
    if len(peaks) == 2: return 2 if peaks[1] - peaks[0] >= 2 else 1
    potentialK = math.ceil(math.sqrt(peaks[-1] - peaks[0]))  
    maxFlags = 0 
    while potentialK > maxFlags: 
        cumDistance = 0 
        flags = 0
        firstFlag = True
        for i in range(1, len(distances)):
            cumDistance  = distances[i]
            if cumDistance >= potentialK: 
                if firstFlag: 
                    flags  = 2 
                    firstFlag = False
                else: 
                    flags  = 1
                cumDistance = 0
        if flags > maxFlags and flags == potentialK: 
            return flags 
        elif flags > maxFlags and potentialK > flags: 
            maxFlags = flags
        potentialK -= 1
    return maxFlags