**Task Score**

**Correctness**

**Performance**

You are given N counters, initially set to 0, and you have two possible operations on them:

increase(X)− counter X is increased by 1,max counter− all counters are set to the maximum value of any counter.

A non-empty array A of M integers is given. This array represents consecutive operations:

- if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
- if A[K] = N + 1 then operation K is max counter.

For example, given integer N = 5 and array A such that:

`A[0] = 3 A[1] = 4 A[2] = 4 A[3] = 6 A[4] = 1 A[5] = 4 A[6] = 4`

the values of the counters after each consecutive operation will be:

`(0, 0, 1, 0, 0) (0, 0, 1, 1, 0) (0, 0, 1, 2, 0) (2, 2, 2, 2, 2) (3, 2, 2, 2, 2) (3, 2, 2, 3, 2) (3, 2, 2, 4, 2)`

The goal is to calculate the value of every counter after all operations.

Write a function:

def solution(N, A)

that, given an integer N and a non-empty array A consisting of M integers, returns a sequence of integers representing the values of the counters.

Result array should be returned as an array of integers.

For example, given:

`A[0] = 3 A[1] = 4 A[2] = 4 A[3] = 6 A[4] = 1 A[5] = 4 A[6] = 4`

the function should return [3, 2, 2, 4, 2], as explained above.

Write an ** efficient** algorithm for the following assumptions:

- N and M are integers within the range [1..100,000];
- each element of array A is an integer within the range [1..N + 1].

*not defined yet*

**Passed**

```
def solution(N, A):
counters = [0] * N
max_val = 0
last_update = 0
n1 = N+1
for i in A:
if i < n1:
if counters[i-1] < last_update:
counters[i-1] = last_update
counters[i-1]+=1
if counters[i-1] > max_val:
max_val = counters[i-1]
else:
last_update = max_val
for i in xrange(N):
if counters[i] < last_update:
counters[i] = last_update
return counters
```

**Failed**

```
def solution(N, A):
counters = [0] * N
max_val = 0
last_update = 0
for X in A:
if 1 <= X <= N:
if counters[X-1] < last_update:
counters[X-1] = last_update
counters[X-1]+=1
if counters[X-1] > max_val:
max_val = counters[X-1]
elif A[K] == (N + 1):
last_update = max_val
for i in xrange(N):
if counters[i] < last_update:
counters[i] = last_update
return counters
```

**Example tests**

**RUNTIME ERROR**, tested program terminated unexpectedly

Traceback (most recent call last): File "user.py", line 131, in <module> main() File "user.py", line 108, in main result = sol.solution ( N, A ) File "/tmp/solution.py", line 13, in solution elif A[K] == (N + 1): NameError: global name 'K' is not defined

**Passed**

```
def solution(N, A):
counters = [0] * N
max_val = 0
last_update = 0
for K,X in enumerate(A):
if 1 <= X <= N:
if counters[X-1] < last_update:
counters[X-1] = last_update
counters[X-1]+=1
if counters[X-1] > max_val:
max_val = counters[X-1]
elif A[K] == (N + 1):
last_update = max_val
for i in xrange(N):
if counters[i] < last_update:
counters[i] = last_update
return counters
```

**Failed**

```
def solution(N, A):
counters = [0] * N
max_val = 0
last_update = 0
for K,X in enumerate(A):
if 1 <= X <= N:
counters[X-1] = min(counters[X-1], last_update)
counters[X-1]+=1
max_val = max(counters[X-1], max_val)
elif A[K] == (N + 1):
last_update = max_val
for i in xrange(N):
counters[i] = min(counters[i], last_update)
return counters
```

**Example tests**

**WRONG ANSWER**, got [1, 0, 1, 1, 0] expected [3, 2, 2, 4, 2]

**Failed**

```
def solution(N, A):
counters = [0] * N
max_val = 0
last_update = 0
for K,X in enumerate(A):
if 1 <= X <= N:
counters[X-1] = min(counters[X-1], last_update)
counters[X-1]+=1
max_val = max(counters[X-1], max_val)
elif A[K] == (N + 1):
last_update = max_val
for i in xrange(N):
if counters[i] < last_update:
counters[i] = last_update
return counters
```

**Example tests**

**WRONG ANSWER**, got [1, 1, 1, 2, 1] expected [3, 2, 2, 4, 2]

**Failed**

```
def solution(N, A):
counters = [0] * N
max_val = 0
last_update = 0
for K,X in enumerate(A):
if 1 <= X <= N:
counters[X-1] = min(counters[X-1], last_update)
counters[X-1]+=1
if counters[X-1] > max_val:
max_val = counters[X-1]
elif A[K] == (N + 1):
last_update = max_val
for i in xrange(N):
if counters[i] < last_update:
counters[i] = last_update
return counters
```

**Example tests**

**WRONG ANSWER**, got [1, 1, 1, 2, 1] expected [3, 2, 2, 4, 2]

**Passed**

```
def solution(N, A):
counters = [0] * N
max_val = 0
last_update = 0
for K,X in enumerate(A):
if 1 <= X <= N:
if counters[X-1] < last_update:
counters[X-1] = last_update
counters[X-1]+=1
if counters[X-1] > max_val:
max_val = counters[X-1]
elif A[K] == (N + 1):
last_update = max_val
for i in xrange(N):
if counters[i] < last_update:
counters[i] = last_update
return counters
```

**Passed**

```
def solution(N, A):
counters = [0] * N
max_val = 0
last_update = 0
for K,X in enumerate(A):
if 1 <= X <= N:
counters[X-1] = max(counters[X-1], last_update)
counters[X-1]+=1
if counters[X-1] > max_val:
max_val = counters[X-1]
elif A[K] == (N + 1):
last_update = max_val
for i in xrange(N):
if counters[i] < last_update:
counters[i] = last_update
return counters
```

**Failed**

```
def solution(N, A):
counters = [0] * N
max_val = 0
last_update = 0
for K,X in enumerate(A):
if 1 <= X <= N:
counters[X-1] = max(counters[X-1], last_update)
counters[X-1]+=1
max_val = min(counters[X-1], max_val)
elif A[K] == (N + 1):
last_update = max_val
for i in xrange(N):
if counters[i] < last_update:
counters[i] = last_update
return counters
```

**Example tests**

**WRONG ANSWER**, got [1, 0, 1, 4, 0] expected [3, 2, 2, 4, 2]

**Passed**

```
def solution(N, A):
counters = [0] * N
max_val = 0
last_update = 0
for K,X in enumerate(A):
if 1 <= X <= N:
counters[X-1] = max(counters[X-1], last_update)
counters[X-1]+=1
max_val = max(counters[X-1], max_val)
elif A[K] == (N + 1):
last_update = max_val
for i in xrange(N):
if counters[i] < last_update:
counters[i] = last_update
return counters
```

**Passed**

```
def solution(N, A):
counters = [0] * N
max_val = 0
last_update = 0
for K,X in enumerate(A):
if 1 <= X <= N:
counters[X-1] = max(counters[X-1], last_update)
counters[X-1]+=1
max_val = max(counters[X-1], max_val)
elif A[K] == (N + 1):
last_update = max_val
for i in xrange(N):
counters[i] = max(counters[i], last_update)
return counters
```

**Passed**

```
def solution(N, A):
counters = [0] * N
max_counter = 0
last_update = 0
for K,X in enumerate(A): # O(M)
if 1 <= X <= N:
counters[X-1] = max(counters[X-1], last_update)
counters[X-1] += 1
max_counter = max(counters[X-1], max_counter)
elif A[K] == (N + 1):
last_update = max_counter
for i in xrange(N): # O(N)
counters[i] = max(counters[i], last_update)
return counters
```

**100**

```
def solution(N, A):
counters = [0] * N
max_counter = 0
last_update = 0
for K,X in enumerate(A): # O(M)
if 1 <= X <= N:
counters[X-1] = max(counters[X-1], last_update)
counters[X-1] += 1
max_counter = max(counters[X-1], max_counter)
elif A[K] == (N + 1):
last_update = max_counter
for i in xrange(N): # O(N)
counters[i] = max(counters[i], last_update)
return counters
```

The solution obtained perfect score.

**O(N + M)**

**Performance tests**

**OK**

**OK**

**OK**

**OK**

**OK**

**OK**