performance - time complexity of initializing an array




initializing an n elements array using O(1) performence? (6)

someone has an idea how can I do that ?

thanks


If you mean "initialize a dense array of N items in a time independent of N", then it is physically impossible. A dense array has a storage space that grows linearly with the number of items, and it will take a linear amount of time to initialize this space.

You can have constant-time initialization using a sparse array. That is essentially an associative array (or hashmap, or dictionary, or table, depending on the language) which initializes items when they are first accessed.


If you need to do something to each element of a set of n elements, you cannot do it with better than O(n) performance.


The following operation is O(n) time:

Arrays.fill(answer, minimumValue);

Now, if you are given a test case where the max counter operation is repeated often (say n/3 of the total operations) - you got yourself an O(n*m) algorithm (worst case analysis), and NOT O(n+m).

You can optimize it to be done in O(n+m) time, by using an algorithm that initializes an array in O(1) every time this operation happens.
This will reduce worst case time complexity from O(n*m) to O(n+m)1


(1)Theoretically, using the same idea, it can even be done in O(m) - regardless of the size of the number of counters, but the first allocation of the arrays takes O(n) time in java


This is a bit like @Eran's solution but encapsulates the functionality in an object. Essentially - keep track of a max value and an atLeast value and let the object's functionality do the rest.

private static class MaxCounter {

    // Current set of values.
    final int[] a;
    // Keeps track of the current max value.
    int currentMax = 0;
    // Min value. If a[i] < atLeast the a[i] should appear as atLeast.
    int atLeast = 0;

    public MaxCounter(int n) {
        this.a = new int[n];
    }

    // Perform the defined op.
    public void op(int k) {
        // Values are one-based.
        k -= 1;
        if (k < a.length) {
            // Increment.
            inc(k);
        } else {
            // Set max
            max(k);
        }
    }

    // Increment.
    private void inc(int k) {
        // Get new value.
        int v = get(k) + 1;
        // Keep track of current  max.
        if (v > currentMax) {
            currentMax = v;
        }
        // Set new value.
        a[k] = v;
    }

    private int get(int k) {
        // Returns eithe a[k] or atLeast.
        int v = a[k];
        return v < atLeast ? atLeast : v;
    }

    private void max(int k) {
        // Record new max.
        atLeast = currentMax;
    }

    public int[] solution() {
        // Give them the solution.
        int[] solution = new int[a.length];
        for (int i = 0; i < a.length; i++) {
            solution[i] = get(i);
        }
        return solution;
    }

    @Override
    public String toString() {
        StringBuilder s = new StringBuilder("[");
        for (int i = 0; i < a.length; i++) {
            s.append(get(i));
            if (i < a.length - 1) {
                s.append(",");
            }
        }
        return s.append("]").toString();
    }
}

public void test() {
    System.out.println("Hello");
    int[] p = new int[]{3, 4, 4, 6, 1, 4, 4};
    MaxCounter mc = new MaxCounter(5);
    for (int i = 0; i < p.length; i++) {
        mc.op(p[i]);
        System.out.println(mc);
    }
    int[] mine = mc.solution();
    System.out.println("Solution = " + Arrays.toString(mine));
}

Subtracting a number from all elements of an array in constant time

You can't change n elements in memory in less than O(n) time, but you can change what that memory represents. If you were to create a custom array class you can include an offset member. When an array element is read you add the offset on demand. When an element is added, you subtract the current offset before storing it in memory (so it is recalled as the correct value when added with the offset). With that layout simply modify the offset in O(1) time and effectively achieve what you are looking for.


What part of my code is making my performance suffer? (Codility's MaxCounter)

Instead of calling Arrays.fill(answer, minimumValue); whenever you encounter a "max counter" operation, which takes O(N), you should keep track of the last max value that was assigned due to "max counter" operation, and update the entire array just one time, after all the operations are processed. This would take O(N+M).

I changed the variables names from min to max to make it less confusing.

public class Solution {

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

        int highestCounter = N;
        int maxValue = 0;
        int lastMaxValue = 0;
        int [] answer = new int[N];

        for (int i = 0; i < A.length; i++) {
            int currentCounter = A[i]; 
            int answerEquivalent = currentCounter -1;

            if(currentCounter >0 && currentCounter<=highestCounter){
                if (answer[answerEquivalent] < lastMaxValue)
                    answer[answerEquivalent] = lastMaxValue +1;
                else 
                    answer[answerEquivalent] = answer[answerEquivalent]+1; 

                if(answer[answerEquivalent] > maxValue){
                    maxValue = answer[answerEquivalent];
                }
            }

            if (currentCounter == highestCounter +1){
                lastMaxValue = maxValue;
            }
        }
        // update all the counters smaller than lastMaxValue
        for (int i = 0; i < answer.length; i++) {
            if (answer[i] < lastMaxValue)
                answer[i] = lastMaxValue;
        }
        return answer;
    }

}




performance