PassingCars in Codility using Python

Question

I have a coding challenge next week as the first round interview. The HR said they will use Codility as the coding challenge platform. I have been practicing using the Codility Lessons.

My issue is that I often get a very high score on Correctness, but my Performance score, which measure time complexity, is horrible (I often get 0%).

Here's the question: https://app.codility.com/programmers/lessons/5-prefix_sums/passing_cars/

My code is:

def solution(A):
    N = len(A)
    my_list = []
    count = 0
    for i in range(N):
        if A[i] == 1:
            continue
        else:
            my_list = A[i + 1:]
            count = count + sum(my_list)
    print(count)
    return count

It is supposed to be O(N) but mine is O(N**2).

1. How can someone approach this question to solve it under the O(N) time complexity?

2. In general, when you look at an algorithm question, how do you come up with an approach?

Answer 1

You should not sum the entire array each time you find a zero. That makes it O(n^2). Instead note that every zero found will give a +1 for each following one:

def solution(A):
    zeros = 0
    passing = 0
    for i in A:
        if i == 0:
            zeros += 1
        else:
            passing += zeros
    return passing