Solution to Codility lesson2-exercise4 Max Counters problem, link to Codility problem and complete solution at the end of the post.

**Definitions:**

In this problem we have the definition of two operations, with a given *N*, and a count array for counting elements from *1 *to* N , *

− counter

is increased by one,

− all counters are set to the maximum value of the count array.

** Problem:**Define a function

*solution*with input

*A*and

*N*, such that

*solution*returns a count array of size

*N*with the results of all operations in the elements of

*A*.

- Expected worst-case time complexity is
*O(N + M)*; - Expected worst-case space complexity is
*O(N)*, beyond input storage (not counting the storage required for input arguments).

**Elements of input arrays can be modified.**** **

### Analysis:

The main strategy to solve this problem within the asked time complexity, is not to update all elements of the counter every time we have a *max counter *operation. We’ll have a variable to remember what was the max counter value at the last *max counter *operation. And we will only update the next counters elements for the next operations.

12 13 14 15 16 17 |
# max counter operation, defines a offset with the value of the max counter of the count array at the time if A[k] > N: offset = max_counter # increase(x) operation, id a max counter operation happened updates the count of the element A[k] accordingly else: count[A[k]] = max(offset + 1, count[A[k]] + 1) |

We also keep track of the max counter at every loop on the iterations in *A*.

19 20 21 |
# Tracks the max counter value of the count array if max_counter < count[A[k]]: max_counter = count[A[k]] |

Visiting every element of *A *so we could execute all the operations gives us an *O(M) *time complexity, because the size of the array *A *is *M**.*

Since the only elements of the count array updated by the *max counter* operation were the ones visited after such operation, we have to update the ones that were not visited.

23 24 25 26 |
# Updates the values that were not updated before by the max counter operation for k in xrange(1, N + 1): if count[k] < offset: count[k] = offset |

We don’t know which elements of the count array were updated, so we visit every element of it. The size of the count array is *N (N + 1 in our implementation, but we are ignoring the index 0, and this could be done with a N size array, we just have to “shift” the counters)* this gives us an *O(N) *time complexity.

Then the total time complexity will be *O(N) + O(M), *which is *O(N + M)*.

For the space complexity we have *O(N) *because the count array has it’s sizes depending on the size of the input *N*.

**Complete Solution:**

1234567891011121314151617181920212223242526272829
# Name: MaxCounters # Link: https://codility.com/demo/take-sample-test/max_counters/ def solution(N, A): M = len(A) count = [0]*(N + 1) max_counter = 0 offset = 0 for k in xrange(M): # max counter operation, defines a offset with the value of the max counter of the count array at the time if A[k] > N: offset = max_counter # increase(x) operation, id a max counter operation happened updates the count of the element A[k] accordingly else: count[A[k]] = max(offset + 1, count[A[k]] + 1) # Tracks the max counter value of the count array if max_counter < count[A[k]]: max_counter = count[A[k]] # Updates the values that were not updated before by the max counter operation for k in xrange(1, N + 1): if count[k] < offset: count[k] = offset return count[1:]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
# Name: MaxCounters # Link: https://codility.com/demo/take-sample-test/max_counters/ def solution(N, A): M = len(A) count = [0]*(N + 1) max_counter = 0 offset = 0 for k in xrange(M): # max counter operation, defines a offset with the value of the max counter of the count array at the time if A[k] > N: offset = max_counter # increase(x) operation, id a max counter operation happened updates the count of the element A[k] accordingly else: count[A[k]] = max(offset + 1, count[A[k]] + 1) # Tracks the max counter value of the count array if max_counter < count[A[k]]: max_counter = count[A[k]] # Updates the values that were not updated before by the max counter operation for k in xrange(1, N + 1): if count[k] < offset: count[k] = offset return count[1:] |

*Time Complexity O(N + M)*

*Space Complexity O(N)*