Codility Lesson4 MaxCounters

Lesson4のMaxCountersは具体例から見た方が理解しやすいと思うので具体例を見ていきましょう。

今回登場するのは次のような要素からなるリストA
A[0] = 3
A[1] = 4
A[2] = 4
A[3] = 6
A[4] = 1
A[5] = 4
A[6] = 4
変数N (今回はN=5とする)
そして長さNのカウンターリストです。
(0,0,0,0,0,0)

まず、配列Aに関して0番目から6番目まで順に要素を確認していきます。
A[0] = 3はN(=5)以下なので3個目のカウンターを+1する。
(0,0,1,0,0)
A[1] = 4はN(=5)以下なので4個目のカウンターを+1する。
(0,0,1,1,0)
A[2] = 4はN(=5)以下なので4個目のカウンターを+1する。
(0,0,1,2,0)
A[3] = 6はN(=5)より大きいので全カウンターを最大カウンターである2にする。
(2,2,2,2,2)
A[4] = 1はN(=5)以下なので1個目のカウンターを+1する。
(3,2,2,2,2)
A[5] = 4はN(=5)以下なので4個目のカウンターを+1する。
(3,2,2,3,2)
A[6] = 4はN(=5)以下なので4個目のカウンターを+1する。
(3,2,2,4,2)

最終的にこのカウンターリストを返すようなプログラムを書くことが目標です。

アルゴリズムは以下の通りです。

1 配列Aの各要素に対して与えられたNとの比較を行いカウンターリストを更新していく。
2 1の操作をAの全要素に対して行う。その際、最大カウンターの値はその都度更新していく。

コードは以下の通りです。

def solution(N,A):
    len_A = len(A)
    counter_list = [0]*N   #カウンターリストの用意　最終的にこれをreturnする
    i = 0
    list_max = 0    #最大カウンターを保持する変数

    while i < len_A:
        if A[i] <= N:
            counter_list[A[i]-1] +=1
            if counter_list[A[i]-1] > list_max:
                list_max = counter_list[A[i]-1] #最大カウンターの更新
        else:
            counter_list = [list_max]*N #A[i]=N+1の時は全要素がlist_maxであるリストに更新する
        i +=1
    return counter_list

さて結果は。。。。？

あれ88%です。。。　計算量がO(N+M)で、どうやら計算時間をもう少し短縮しろと怒られているんですがこれ以上短縮する方法があるのでしょうか。。？わかる方いたら教えてください。