MaxCounters

Calculate the values of counters after applying all alternating operations: increase counter by 1; set value of all counters to current maximum
ℹ️ © Codility, 2009-2018

Problem

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,
• maxcounter − 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 maxcounter.

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

Assume that:
• 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].

Complexity:
• expected worst-case time complexity is O(n + m);
• expected worst-case space complexity is O(n) (not counting the storage required for input arguments).

Solution

C#

using System;
class Solution {
  public int[] solution(int n, int[] A) {
    int[] R = new int[n];
    for (int i = 0; i < n; i++) {
      R[i] = 0;
    }
    int min = 0;
    int max = 0;
    int m = A.Length;
    for (int k = 0; k < m; k++) {
      if (A[k] <= n) {
        if (R[A[k] - 1] < min + 1) {
          R[A[k] - 1] = min + 1;
        } else {
          R[A[k] - 1]++;
        }
        if (R[A[k] - 1] > max) {
          max = R[A[k] - 1];
        }
      } else {
        min = max;
      }
    }
    for (int i = 0; i < n; i++) {
      if (R[i] < min) {
        R[i] = min;
      }
    }
    return R;
  }
}

Java

class Solution {
  public int[] solution(int n, int[] A) {
    int[] R = new int[n];
    for (int i = 0; i < n; i++) {
      R[i] = 0;
    }
    int min = 0;
    int max = 0;
    int m = A.length;
    for (int k = 0; k < m; k++) {
      if (A[k] <= n) {
        if (R[A[k] - 1] < min + 1) {
          R[A[k] - 1] = min + 1;
        } else {
          R[A[k] - 1]++;
        }
        if (R[A[k] - 1] > max) {
          max = R[A[k] - 1];
        }
      } else {
        min = max;
      }
    }
    for (int i = 0; i < n; i++) {
      if (R[i] < min) {
        R[i] = min;
      }
    }
    return R;
  }
}

JavaScript

function solution(n, A) {
  let R = [];
  for (let i = 0; i < n; i++) {
    R[i] = 0;
  }
  let m = A.length;
  let min = 0;
  let max = 0;
  for (let k = 0; k < m; k++) {
    if (A[k] <= n) {
      if (R[A[k] - 1] < min + 1) {
        R[A[k] - 1] = min + 1;
      } else {
        R[A[k] - 1]++;
      }
      if (R[A[k] - 1] > max) {
        max = R[A[k] - 1];
      }
    } else {
      min = max;
    }
  }
  for (let i = 0; i < n; i++) {
    if (R[i] < min) {
      R[i] = min;
    }
  }
  return R;
}

PHP

function solution($n, $A) {
  $R = [];
  for ($i = 0; $i < $n; $i++) {
    $R[$i] = 0;
  }
  $m = count($A);
  $min = 0;
  $max = 0;
  for ($k = 0; $k < $m; $k++) {
    if ($A[$k] <= $n) {
      if ($R[$A[$k] - 1] < $min + 1) {
        $R[$A[$k] - 1] = $min + 1;
      } else {
        $R[$A[$k] - 1]++;
      }
      if ($R[$A[$k] - 1] > $max) {
        $max = $R[$A[$k] - 1];
      }
    } else {
      $min = $max;
    }
  }
  for ($i = 0; $i < $n; $i++) {
    if ($R[$i] < $min) {
      $R[$i] = $min;
    }
  }
  return $R;
}