Algorithm: Max Counters

Question

I have the following 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 zero-indexed 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.

I did the following solution but it runs at O(NK) where K = length of array A.

public int[] solution(int N, int[] A) {
    int[] result = new int[N];
    int maximum = 0;

    for (int K = 0; K < A.Length; K++)
    {
        if (A[K] < 1 || A[K] > N + 1)
            throw new InvalidOperationException();

        if (A[K] >= 1 && A[K] <= N)
        {
            result[A[K] - 1]++;

            if (result[A[K] - 1] > maximum)
            {
                maximum = result[A[K] - 1];
            }
        }
        else
        {
            // inefficiency here
            for (int i = 0; i < result.Length; i++)
                result[i] = maximum;
        }
    }

    return result;
}

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!

Answer 1

This is what I came up with, but I am not sure if it works 100%:

public int[] solution(int N, int[] A) {
    int[] result = new int[N];
    int maximum = 0;
    int resetLimit = 0;

    for (int K = 0; K < A.Length; K++)
    {
        if (A[K] < 1 || A[K] > N + 1)
            throw new InvalidOperationException();

        if (A[K] >= 1 && A[K] <= N)
        {
            if (result[A[K] - 1] < resetLimit) {
                result[A[K] - 1] = resetLimit + 1;
            } else {
                result[A[K] - 1]++;
            }

            if (result[A[K] - 1] > maximum)
            {
                maximum = result[A[K] - 1];
            }
        }
        else
        {
            // inefficiency here
            //for (int i = 0; i < result.Length; i++)
            //    result[i] = maximum;
            resetLimit = maximum;
        }
    }

    for (int i = 0; i < result.Length; i++)
        result[i] = Math.Max(resetLimit, result[i]);

    return result;
}

Answer 2

Remember:

"Making your code readable is as important as making it executable."

-- Robert C Martin

Even when trying to solve a hard problem...

So trying to achieve a better readability I've created a class to encapsulate the counters array and its operations (Law of Demeter). Sadly my first solution got only 60% in the performance test, so at the cost of a bit of readability I've improved it with a smarter solution and finally got 100%.

Here are my two implementations with comments:

O(N*M) Correctness 100% / Performance 60% (high redability)

//I didn't refactored the names of the variables N and A
//to maintain it aligned with the question description
public int[] solution(int N, int[] A)
{
    var counters = new Counters(N);

    for (int k = 0; k < A.Length; k++)
    {
        if (A[k] <= N)
            counters.IncreaseCounter(A[k]);
        else
            counters.MaxAllCounters();
    }

    return counters.ToArray();
}

public class Counters
{
    private int[] counters;
    private int greaterValueInCounter = 0;

    public Counters(int length)
    {
        counters = new int[length];
    }

    public void MaxAllCounters()
    {
        for (int i = 0; i < counters.Length; i++)
        {
            counters[i] = greaterValueInCounter;
        }
    }

    public void IncreaseCounter(int counterPosition)
    {
        //The counter is one-based, but our array is zero-based
        counterPosition--;

        //Increments the counter
        counters[counterPosition]++;

        if (counters[counterPosition] > greaterValueInCounter)
            greaterValueInCounter = counters[counterPosition];
    }

    //The counters array is encapsuled in this class so if we provide external 
    //acess to it anyone could modify it and break the purpose of the encapsulation
    //So we just exposes a copy of it :)
    public int[] ToArray()
    {
        return (int[])counters.Clone();
    }
} 

Codility result

O(N+M) Correctness 100% / Performance 100% (not so high redability)

Note the beauty of the encapsulation: to improve the algorithm I just have to edit some methods of the Counters class without changing a single character on the solution method.

Methods edited in the Counters class:

• IncreaseCounter()
• MaxAllCounters()
• ToArray()

Final code:

//Exactly the same code
public int[] solution(int N, int[] A)
{
    var counters = new Counters(N);

    for (int k = 0; k < A.Length; k++)
    {
        if (A[k] <= N)
            counters.IncreaseCounter(A[k]);
        else
            counters.MaxAllCounters();
    }

    return counters.ToArray();
}

public class Counters
{
    private int[] counters;
    private int greaterValueInCounter = 0;
    private int currentEquilibratedScore = 0;

    public Counters(int length)
    {
        counters = new int[length];
    }

    public void MaxAllCounters()
    {
        //We don't update the entire array anymore - that was what caused the O(N*M)
        //We just save the current equilibrated score value
        currentEquilibratedScore = greaterValueInCounter;
    }

    public void IncreaseCounter(int counterPosition)
    {
        //The counter is one-based, but our array is zero-based
        counterPosition--;

        //We need to add this "if" here because with this new solution the array
        //is not always updated, so if we detect that this position is lower than
        //the currentEquilibratedScore, we update it before any operation
        if (counters[counterPosition] < currentEquilibratedScore)
            counters[counterPosition] = currentEquilibratedScore + 1;
        else
            counters[counterPosition]++;

        if (counters[counterPosition] > greaterValueInCounter)
            greaterValueInCounter = counters[counterPosition];
    }

    //The counters array is encapsuled in this class so if we provide external 
    //acess to it anyone could modify it and break the purpose of the encapsulation
    //So we just exposes a copy of it :)
    public int[] ToArray()
    {
        //Now we need to fix the unupdated values in the array
        //(the values that are less than the equilibrated score)
        for (int i = 0; i < counters.Length; i++)
        {
            if (counters[i] < currentEquilibratedScore)
                counters[i] = currentEquilibratedScore;
        }

        return (int[])counters.Clone();
    }
}

Codility result

Answer 3

def solution(N, A):
    # write your code in Python 2.6
    res = [0] * N
    m = 0
    minValue = 0
    for x in A:
        if 1 <= x <= N:
            res[x - 1] = max(res[x - 1], minValue) + 1
            if res[x - 1] > m:
                m = res[x - 1]
        else:
            minValue = m
    for i in xrange(N):
        res[i] = max(res[i], minValue)
    return res

Answer 4

Here's a solution I came up with in Python (100/100 on codility); it's a little different than others I've seen on here so thought I'd share:

def solution(N, A):
    count = [0] * N
    max_counter = [i for i, a in enumerate(A) if a == N+1]
    if len(max_counter) == len(A):
        return count
    if max_counter:
        mode = 0
        for i, m in enumerate(max_counter):
            if m == 0 or m - max_counter[i-1] == 1:
                continue
            subcount = {}
            if i == 0:
                for k in A[:m]:
                    if k not in subcount:
                        subcount[k] = 1
                    else:
                        subcount[k] += 1
            else:
                for k in A[max_counter[i-1]+1:m]:
                    if k not in subcount:
                        subcount[k] = 1
                    else:
                        subcount[k] += 1
            mode += max(subcount.values())
        count = [mode] * N
        for k in A[max_counter[-1]+1:]:
            count[k-1] += 1
    else:
        for k in A:
            count[k-1] += 1
    return count

Answer 5

Let's see...

public int[] Solution(int N, int[] A)
{
    int[] data = new int[N];
    int maxval = 0;
    int baseval = 0;
    for (int K = 0; K < A.length; K++)
    {
        int index = A[K] - 1;
        if (index < 0 || index > N)
            throw new InvalidOperationException();

        if (index < N)
            maxval = baseval + Math.Max(maxval, ++data[index]);
        else
        {
            baseval = maxval;
            data = new int[N];
        }
    }

    for (int K = 0; K < N; K++)
        data[K] += baseval;

    return data;
}

I think that's O(N+K). Depends on how you count the Order of re-initializing the array.

Answer 6

Same principle as everybody scoring 100% really, it is just that I find this version easier to read (and it is probably only because I wrote it).

using System;
using System.Linq;

class Solution 
{
    public int[] solution(int N, int[] A) 
    {

        var currentMax = 0;
        var resetValue = 0;
        var counters = Enumerable.Range(1, N).ToDictionary(i => i, i => 0);

        foreach (var a in A)
        {
            if (a == N + 1) resetValue = currentMax;
            else
            {
                counters[a] = Math.Max(counters[a], resetValue) + 1;
                currentMax = Math.Max(currentMax, counters[a]);
            }
        }
        return counters.Values.Select(v => Math.Max(v,resetValue)).ToArray();
    }
}

Answer 7

Swift solution 100%

public func solution(_ N : Int, _ A : inout [Int]) -> [Int] {
    // write your code in Swift 4.2.1 (Linux)

    var solution = Array.init(repeating: 0, count: N)

        var max = 0
        var actualMaxValue = 0

        for obj in A {

            if (obj <= N && obj >= 1 ) {

                if solution[obj-1] < actualMaxValue {

                    solution [obj-1] = actualMaxValue + 1
                } else {

                    solution[obj-1] += 1
                }

                if (solution[obj-1] > max) {

                    max = solution[obj-1]
                }
            }
            else if obj == N+1 {

              actualMaxValue = max
            }
        }

    for (index, value) in solution.enumerated() {


        if value < actualMaxValue {

            solution[index] = actualMaxValue
        }
    }


    return solution
}

Answer 8

Here is an implementation in PHP:

function solution($N, $A) {
    $output = array_fill(0, $N, 0);
    $maxCounter = 0;
    $minCounter = 0;
    foreach ($A as $number) {
        if($number === $N + 1) {
            $minCounter = $maxCounter;
        } else if($number <= $N) {
            $number--;
            if($minCounter > $output[$number]) {
                $output[$number] = $minCounter;
            }
            $output[$number]++;
            if($output[$number] > $maxCounter) $maxCounter = $output[$number];
        }
    }

    foreach ($output as $index => $number) {
        if($number < $minCounter) $output[$index] = $minCounter;
    }

//    var_dump($output);
    return $output;
}

Answer 9

public int[] counters(int N, int[] A)
{
    int[] count = new int[N];
    int maxCount = 0;
    int setAll = 0;

    for (int i = 0; i < A.Length; i++)
    {
        if (A[i] == N + 1)
        {
            setAll += maxCount;
            maxCount = 0;
            count = new int[N];
        }
        else
        {
            count[A[i] - 1] += 1;


            if (count[A[i] - 1] > maxCount)
            {
                maxCount = count[A[i] - 1];
            }
        }
    }

    for (int j = 0; j < count.Length; j++)
    {
        count[j] += setAll;
    }

    return count;
}

I think this is O(N+K), but codility say its O(N*K)? Would appreciate if anyone could explain which is correct...

Answer 10

A 100/100 solution in php

function solution($N, $A){
    $cond     = $N + 1;
    $cur_max  = 0;
    $last_upd = 0;
    $cnt_arr  = array();
    $cnt      = count($A);
    for($i = 0; $i < $cnt; $i++){
        $cur = $A[$i];
        if($cur == $cond){
            $last_upd = $cur_max;
        }
        else{
            $pos = $cur - 1;
            if(!isset($cnt_arr[$pos])){
                $cnt_arr[$pos] = 0;
            }
            if($cnt_arr[$pos] < $last_upd){
                $cnt_arr[$pos] = $last_upd + 1;
            }
            else{
                $cnt_arr[$pos] ++;
            }
            if($cnt_arr[$pos] > $cur_max){
                $cur_max = $cnt_arr[$pos];
            }
        }
    }
    for($i = 0; $i < $N; $i++){
        if(!isset($cnt_arr[$i])){
            $cnt_arr[$i] = 0;
        }
        if($cnt_arr[$i] < $last_upd){
            $cnt_arr[$i] = $last_upd;
        }
    }
    return $cnt_arr;
}

Answer 11

Rue, I just ran this locally. Watched the counters myself. I used this algorithm:

    public int[] solution(int N, int[] A)
    {
        int[] result = new int[N];
        int maximum = 0;
        int resetlimit = 0;

        for (int K = 0; K < A.Length; K++)
        {
            if (A[K] < 1 || A[K] > N + 1)
            {
                throw new InvalidOperationException();
            }

            if (A[K] >= 1 && A[K] <= N)
            {
                if (result[A[K] - 1] < resetlimit)
                {
                    result[A[K] - 1] = resetlimit + 1;
                }
                else
                {
                    result[A[K] - 1]++;
                }

                if (result[A[K] - 1] > maximum)
                {
                    maximum = result[A[K] - 1];
                }
            }
            else
            {
                resetlimit = maximum;
                result = Enumerable.Repeat(maximum, result.Length).ToArray();
            }
        }

        //for (int i = 0; i < result.Length; i++)
        //{
        //    result[i] = Math.Max(resetlimit, result[i]);
        //}

        return result;
    }
}

looking at the problem and the result sets, you must include in the inefficient for loop in the else statement. The for loop outside does not replicate the 2nd operation
•if A[K] = N + 1 then operation K is max_counter.

In order for iteration A[3] = 6 to set result[] all to '2' you must load the result array with the maximum counter. Otherwise your return will never have (2,2,2,2,2) as the 4th example array shows.

I too must take a test to get my dream job so the little inefficiency here is important;

the statement

  result = Enumerable.Repeat(maximum, result.Length).ToArray();

loads the array all in one shot so no inner loop and no inner efficiency. I think that is pretty close to the correct result sets. I'm surprised they didn't ask to return like a jagged array of the total return. Still, this codility test scares me a lot.

Answer 12

C++11 code:

#include <algorithm>

vector<int> solution(int N, vector<int> &A) {

    vector<int> hist(N, 0);

    int last_update = 0;
    int max_value = 0;

    for (auto i : A){

        if (1 <= i && i <= N){
            int& val = hist[i - 1];

            if (val < last_update)
                val = last_update + 1;
            else
                val++;

            if (max_value < val)
                max_value = val;
        }

        if (i == (N+1)){
            last_update = max_value;
        }

    }

    replace_if(hist.begin(), hist.end(), [last_update](int x){return x < last_update;}, last_update);

    return hist;
}

Answer 13

The key is that [0] * N is an N operation. If that exists in a for loop it will become N*M. Tested in Codility 100%

            # you can write to stdout for debugging purposes, e.g.
            # print "this is a debug message"

            def solution(N, A):
                # write your code in Python 2.7
                count = [0] * N
                maxCounter = 0
                minCounter = 0
                for x in A:
                    if x <= N and x >= 1:
                        count[x-1] = max(count[x-1], minCounter) + 1
                        if maxCounter < count[x-1]:
                            maxCounter = count[x-1]
                    if x == N + 1:
                        minCounter = maxCounter                
                for i in xrange(N):
                    count[i] = max(count[i], minValue)
                return count

Answer 14

Here is Scala version, 100% on codility:

import java.util

def solution(N: Int, A: Array[Int]): Array[Int] = {

    var counters = new Array[Int](N)

    var maxCounter = 0

    for(ind <- 0 to A.length-1){


      if(A(ind) == (N+1)){

        //all to max
        util.Arrays.fill(counters,maxCounter)

      }else{
        //ind -1  cause array index start with 0 which is marked as 1 in the input data
        counters(A(ind)-1) += 1

        //update max counter if necessary
        if(maxCounter< (counters(A(ind)-1))) maxCounter = (counters(A(ind)-1))

      }

    }

    return counters
  }

Performance: https://codility.com/demo/results/trainingKJT6Y3-74G/

Answer 15

Ruby Codility Code that got 100/100

def solution(a)

  if a.length < 3
      0
  end
  a.sort!
  for i in 2..a.length - 1
    if (a[i-2] + a[i-1]) > a[i]
      return 1
    end
  end
 0
end

Answer 16

def solution(N, A):
    res = [0] * N
    maxV, minV = 0, 0
    for x in A:
        if 1 <= x <= N:
            res[x-1] = max(res[x-1], minV) + 1
            maxV = max(maxV, res[x-1])
        else: minV = maxV
    for i in range(N):
        res[i] = max(res[i], minV)
    return res

Answer 17

Ruby 100%

def solution(n, a)
  max = 0
  offsets = a.inject(Hash.new(max)) do |acc, el|
    next Hash.new(max) if el == n+1
    acc[el] +=1
    max = acc[el] if max < acc[el]
    acc
  end
  (1..n).map{|i| offsets[i]}
end

Answer 18

Here is the kotlin version, 100% on codility

fun solutionMissingInteger(N: Int, A: IntArray): IntArray {
    val counters = IntArray(N)
    var max = 0
    var lastUpdate = 0
    for (index in A.indices) {
        val element = A[index]
        if (element == N + 1) {
            lastUpdate = max
        } else {
            val position = element - 1
            if (counters[position] < lastUpdate) {
                counters[position] = lastUpdate + 1
            } else {
                counters[position] = counters[position] +1
            }

            if (counters[position] > max) {
                max = counters[position]
            }
        }
    }
    setAllCountersToMaxValue(lastUpdate, counters)
    return counters
}

private fun setAllCountersToMaxValue(lastUpdate: Int, counters: IntArray) {
    for (index in counters.indices) {
        if (counters[index] < lastUpdate)
            counters[index] = lastUpdate
    }
}

Answer 19

with js max score that I can get is 77%

any improvement?

function solution(N, A) {

  let counters = [];

  //fill counter with 0
  for (let i = 0; i < N; i += 1) {
    counters[i] = 0;
  }

  //loop array and set counters
  for (let i = 0; i < A.length; i += 1) {

    //0 index fix
    let position = A[i] - 1;

    if (A[i] <= N) {
      counters[position] += 1;
    } else {
      let max = Math.max(...counters);
      counters.fill(max)
    }

  }

  return counters;

}

Answer 20

Java, 100%/100%

public int[] solution(int N, int[] A) {


    int[] counters = new int[N];

    int currentMax = 0;
    int sumOfMaxCounters = 0;
    boolean justDoneMaxCounter = false;

    for (int i = 0; i < A.length ; i++) {

        if (A[i]  <= N) {

            justDoneMaxCounter = false;
            counters[A[i]-1]++;
            currentMax = currentMax < counters[A[i]-1] ? counters[A[i]-1] : currentMax;

        }else if (!justDoneMaxCounter){

            sumOfMaxCounters += currentMax;     
            currentMax = 0;
            counters = new int[N];
            justDoneMaxCounter = true;

        }
    }


    for (int j = 0; j < counters.length; j++) {
        counters[j] = counters[j] + sumOfMaxCounters;
    }

    return counters;
}

Answer 21

A 100% JavaScript solution

function solution(N, A) {
    // initialize all counters to 0
    let counters = Array(N).fill(0)

    // The maximum value of the counter is 0
    let max = 0

    // This variable will determine if an increment all operation has been encountered
    // and its value determines the maximum increment all operation encountered so far
    // for start it is 0, and we will set it to the value of max when A[i] == N + 1
    let max_all = 0

    for(let i = 0; i < A.length; i++) {

        if(A[i] <= counters.length) {

            // if the value of A[i] is 1, we have to increment c[0]
            // and hence the following index
            const c_index = A[i] - 1

            // if max all operation was found previously,
            // we have to set it here, because we are not setting anything in the else section
            // we are just setting a flag in the else section
            // if its value however is greater than max_all, it probably was already maxed
            // and later incremented, therefore we will skip it
            if(counters[c_index] < max_all) counters[c_index] = max_all

            // do the increment here
            const v = ++counters[c_index]

            // update the max if the current value is max
            max = v > max ? v : max
        }

        // this is straight forward
        else max_all = max
    }

    // if there are remaining items that have not been set to max_all inside the loop
    // we will update them here.
    // and we are updating them here instead of inside the for loop in the else section
    // to make the running time better. If updated inside the loop, we will have a running time of M * N
    // however here it's something like (M + N) ~ O(N)
    if(max_all) counters = counters.map(v => v < max_all ? max_all : v)

    // return the counters
    return counters
}

Answer 22

ES6

const solution = (n, a) => {
    // Initialize to zero
    let counter =  new Array(n);
    for(let i = 0  ; i < n ; i++ ){
        counter[i] = 0;
    }
    let max = 0;
    for(let j = 0  ; j < a.length ; j++ ){
        const item = a[j];
        if( item > n) {
            for(let i = 0  ; i < n ; i++ ){
                counter[i] = max;
            }
        }
        else{
            counter[item-1]++; 
            if(max < counter[item-1])
            {
                max = counter[item-1];
            }
        }
    }
    return counter;
};