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

Definitions:

    \[\mathbf{A} = \{x \in \mathbb{N}\ |1\leq x \leq N + 1\wedge |A| = M \},\mathbf{A}\, is\, a\, multiset.\]

    \[\{N,M \in \mathbb{N}\ |\ 1 \leq N,M \leq 100,000\}\]

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 ,

    \[f(x) = \left\{ \begin{array}{ll} increase(x)& \mbox{if } x \leq N\\ max\,counter& \mbox{if } x =N + 1 \end{array} \right.\]

 

  •     \[increase(x)\]

    − counter

        \[x\]

    is increased by one,

  •     \[max\, counter\]

    − 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.

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

Visiting every element of 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.

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:

Time Complexity O(N + M)
Space Complexity O(N)

Link to GitHub solution here .
Link to Codility problem here .

/*Comment here*/