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] = 4the 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] = 4the 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].
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
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
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
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
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
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
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
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
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
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
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
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
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
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.