Max Counters (a problem on counting elements)

MaxCounters

Calculate the values of counters after applying all alternating operations: increase counter by 1; set value of all counters to current maximum.

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,

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.

Write a function:

def solution(N, A)

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.

Write an efficient algorithm for the following assumptions:

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

Example

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.

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

Hint: Let’s analyze the Brute-Force Solution

In Brute-Force solution, we follow the instructions as given.

We increase the counters on encountering the increase operation.

And on encountering the maxCounter() operation, we loop over the counters and set them equal to max counter.

This would solve the problem but would result in a quadratic time complexity.

Hint: Worst Case Scenario For Brute Force Solution. Time Complexity of: N*M

Hint: Linear Time Complexity

The bottleneck for the code is the maxCounter() operation. So, in this solution we find a smart way of implementing the maxCounter() operation.

We would draw an analogy between our counters and racers on a race track.

We would maintain two variables:

1. startLine: that tracks the where the racers are starting.

Basically, on encountering the maxCounter() operation, we would update this field.

2. currentMax: That tracks the maximum value among the counters.

This variable will be used to update the other variable startLine on encountering a maxCounter() operation.

Hint: Linear Time Solution

Hint: What happens when we encounter a maxCounter() op? We update our startLine.

Code

def increase(X, counters, startLine, currentMax):
  if counters[X] < startLine:
      counters[X] = startLine 
  counters[X] += 1
  if counters[X] > currentMax:
      currentMax = counters[X]
  return counters, currentMax
def maxCounter(startLine, currentMax):
  startLine = currentMax
  return startLine 
def solution(N, A):
  startLine = 0
  currentMax = 0
  counters = [0 for i in range(N)]
  
  for i in A:
      if i < N+1:
          counters, currentMax = increase(i-1, counters, startLine, currentMax)
      else:
          startLine = maxCounter(startLine, currentMax)
          
  for i in range(len(counters)):
      if counters[i] < startLine:
          counters[i] = startLine 
  return counters

Detected time complexity: O(N + M)

Test Cases

Correctness tests

extreme_small: all max_counter operations

single: only one counter

small_random1: small random test, 6 max_counter operations

small_random2: small random test, 10 max_counter operations

Performance tests

medium_random1: medium random test, 50 max_counter operations

medium_random2: medium random test, 500 max_counter operations

large_random1: large random test, 2120 max_counter operations

large_random2: large random test, 10000 max_counter operations

extreme_large: all max_counter operations