Introduction

The Codility Max Counters problem looks simple until you try the obvious solution. Incrementing one counter is cheap, but the “set all counters to the current maximum” operation becomes expensive if you eagerly update the whole array every time. The efficient solution uses lazy updates so the whole algorithm stays linear.

The Problem Shape

You have N counters, all starting at 0, and an array of operations A.

Each value in A means one of two things:

• if 1 <= A[K] <= N, increase counter A[K] - 1
• if A[K] == N + 1, set all counters to the maximum current counter value

The naive solution updates every counter on each max operation, which can degrade to O(N * M).

The Key Optimization: Lazy Max Updates

The trick is to avoid writing the max value into every counter immediately. Instead, keep two extra values:

• 'currentMax: the highest counter value seen so far'
• 'baseline: the value all counters should be at least equal to after the latest max operation'

When you later touch an individual counter, first bring it up to baseline if it was left behind.

That turns repeated full-array writes into cheap comparisons.

Java Implementation

Here is the standard linear-time approach.

1import java.util.Arrays;
2
3public class MaxCounters {
4    public static int[] solution(int n, int[] a) {
5        int[] counters = new int[n];
6        int currentMax = 0;
7        int baseline = 0;
8
9        for (int op : a) {
10            if (1 <= op && op <= n) {
11                int index = op - 1;
12
13                if (counters[index] < baseline) {
14                    counters[index] = baseline;
15                }
16
17                counters[index]++;
18
19                if (counters[index] > currentMax) {
20                    currentMax = counters[index];
21                }
22            } else if (op == n + 1) {
23                baseline = currentMax;
24            }
25        }
26
27        for (int i = 0; i < n; i++) {
28            if (counters[i] < baseline) {
29                counters[i] = baseline;
30            }
31        }
32
33        return counters;
34    }
35
36    public static void main(String[] args) {
37        int[] result = solution(5, new int[] {3, 4, 4, 6, 1, 4, 4});
38        System.out.println(Arrays.toString(result));
39    }
40}

Output:

[3, 2, 2, 4, 2]

Why It Works

Suppose a max operation happens when currentMax is 7. Instead of writing 7 into every slot, the algorithm sets baseline = 7.

Later, when a specific counter is incremented, the code checks whether that counter is still below baseline. If it is, the counter is first synchronized to baseline, then incremented.

At the very end, one final pass updates any untouched counters that still trail the last baseline.

That gives the same final result as the naive approach without paying repeated full-array update costs.

Complexity

The runtime is O(N + M):

• one pass through the operations array
• one final pass through the counters

The space complexity is O(N) for the counters array.

This is exactly the improvement Codility is testing for.

Common Pitfalls

A common mistake is eagerly applying the max operation to every counter. That is correct but too slow for large inputs.

Another mistake is forgetting to synchronize a counter with baseline before incrementing it. If you skip that, counters that missed earlier max operations stay too small.

A third issue is forgetting the final cleanup pass. Some counters may never be touched again after the last max operation, so they still need to be raised to the baseline before returning the answer.

Summary

• The naive algorithm is too slow because max operations can update the full array repeatedly
• The efficient solution uses lazy propagation with currentMax and baseline
• Synchronize a counter with baseline only when it is touched or during the final pass
• The optimized runtime is O(N + M)
• This problem is mainly about recognizing and implementing deferred updates correctly