title: Algorithm: Max Counters
body: <p>I have the following problem:</p>
  
  <p>You are given N counters, initially set to 0, and you have two possible operations on them:</p>
  
  <ul>
  <li>increase(X) − counter X is increased by 1, </li>
  <li>max_counter − all counters are set to the maximum value of any counter.</li>
  </ul>
  
  <p>A non-empty zero-indexed array A of M integers is given. This array represents consecutive operations:</p>
  
  <ul>
  <li>if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),</li>
  <li>if A[K] = N + 1 then operation K is max_counter.</li>
  </ul>
  
  <p>For example, given integer N = 5 and array A such that:</p>
  
  <pre><code>A[0] = 3
  A[1] = 4
  A[2] = 4
  A[3] = 6
  A[4] = 1
  A[5] = 4
  A[6] = 4
  </code></pre>
  
  <p>the values of the counters after each consecutive operation will be:</p>
  
  <pre><code>(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)
  </code></pre>
  
  <p>The goal is to calculate the value of every counter after all operations.</p>
  
  <p>I did the following solution but it runs at O(NK) where K = length of array A.</p>
  
  <pre><code>public int[] solution(int N, int[] A) {
      int[] result = new int[N];
      int maximum = 0;
  
      for (int K = 0; K &lt; A.Length; K++)
      {
          if (A[K] &lt; 1 || A[K] &gt; N + 1)
              throw new InvalidOperationException();
  
          if (A[K] &gt;= 1 &amp;&amp; A[K] &lt;= N)
          {
              result[A[K] - 1]++;
  
              if (result[A[K] - 1] &gt; maximum)
              {
                  maximum = result[A[K] - 1];
              }
          }
          else
          {
              // inefficiency here
              for (int i = 0; i &lt; result.Length; i++)
                  result[i] = maximum;
          }
      }
  
      return result;
  }
  </code></pre>
  
  <p>Could anyone show me how this can be better done with O(N + K) where K is the length of array A? Sorry for may terrible coding, I am doing these exercises to improve my programming. Thanks!</p>