Codility MaxCounters  

by ne on 2022-02-16 under Algo/DS/Problems tagged with codility

Hi,
The problem description is in the comments above the solution below.

The problem belongs to Codility, you can try out it yourself on their platform.


/**
 * 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] = 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.
 */

import java.util.Arrays;

public class MaxCounters {

    public static int[] solution(int N, int[] A) {
        int[] arr = new int[N];
        int lastMax = 0, base = 0;
        for (int i = 0; i < A.length; i++) {
            int k = A[i] - 1;
            if (k == N) {
                base = lastMax;
            } else {
                if (arr[k] < base) {
                    arr[k] = base + 1;
                } else {
                    arr[k]++;
                }
                if (lastMax < arr[k]) {
                    lastMax = arr[k];
                }
            }
        }
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < base) {
                arr[i] = base;
            }
        }
        return arr;
    }

    public static void main(String... args) {
        System.out.println(Arrays.toString(solution(5, new int[]{3, 4, 4, 6, 1, 4, 4, 6, 1, 2})));
        System.out.println(Arrays.toString(solution(1, new int[]{2, 1, 1, 2, 1})));

    }
}