pivot.py

[ruidazeng]

I have a very similar Pythonic solution to pivot (https://open.kattis.com/problems/pivot) by traversing the lists twice. Adding the candidates when going left to right then removing the candidates right to left (as shown below). The complexity is O(2N) but should round up to O(N). However, my solution failed with "TLE" message.

Is your solution able to successful pass the time limit on Kattis?

_ = int(input())
listy = [int(x) for x in input().split()]

max_left = -2147483647 # smallest 32-bit signed integers
min_right = 2147483647 # largest 32-bit signed integers
pivots = []

for left_iter in listy:
    if left_iter > max_left:
        pivots.append(left_iter)
    if left_iter > max_left:
        max_left = left_iter

        
for right_iter in listy[::-1]:
    if right_iter > min_right and right_iter in pivots:
        pivots.remove(right_iter)
    if right_iter < min_right:
        min_right = right_iter

print(len(pivots))

[iandioch]

Hi, I believe pivots.remove(right_iter) is an O(N) operation, making this solution O(N^2).

I wrote a detailed rundown of this problem on my blog if you're curious: http://mycode.doesnot.run/2018/04/11/pivot/

[ruidazeng]

Thank you for letting me know!!

I studied your blog and re-evaluated my solution again. I made two minor edits and was able to AC with a CPU time of 0.08s.

After putting it into a function. The solution did ran in 0.06s. I have copied my solution below, all I did was using 2 lists instead of remove and find the intersection (which is a much faster operation).

def main():
    _ = int(input())
    listy = [int(x) for x in input().split()]

    max_left = -2147483647 # smallest 32-bit signed integers
    min_right = 2147483647 # largest 32-bit signed integers
    pivots = []
    candidates = []

    for left_iter in listy:
        if left_iter > max_left:
            pivots.append(left_iter)
            max_left = left_iter

        
    for right_iter in listy[::-1]:
        if right_iter < min_right:
            candidates.append(right_iter)
            min_right = right_iter

    # Common elements comparison between 2 lists (fast)
    common = list(set(pivots).intersection(candidates))
    print(len(common))

if __name__ == '__main__':  
    main()

Thanks again for your advice! I couldn't have done it without you.