Codility NailingPlanks - Solution with linear time complexity

This is a solution with O(N+M) time complexity to Codility NailingPlanks task. The code is written in Java.

This solution first discards all planks that completely wrap other planks, because the nail used for a wrapped plank can be used for all planks that wrap it. For example, consider the three planks below:

Nail 15 is the minimum nail for plank 2. Planks 1 and 3 can use nails 5 and 10 respectively, but it does not matter because nail 15 must be used for plank 2, and thus it determines the minimum nail for all three planks, so planks 1 and 3 can be eliminated from the calculation.

Once all wrapper planks are eliminated, the remaining planks (maximum 2*M of them) are positioned as below:

That means that plank which starts first will also end first, which makes queue a perfect data structure to store the information when traversing the remaining planks.

Elimination of wrapper planks can be done in two steps:

1) Sorting the planks by start position and eliminating planks that start at the same position by taking the shortest plank for each start position. This is basically a variation of counting sort, with linear time complexity:

int[] planks = new int[2 * C.length + 1];
for (int i = 0; i < A.length; i++) {
    if (planks[A[i]] == 0 || B[i] < planks[A[i]]) {
        planks[A[i]] = B[i];
    }
}

After this loop planks[i] contains end position for a plank that starts at the position i.

2) Filtering out wrapper planks:

Queue stack = new Queue(2 * C.length);
for (int i = 1; i < planks.length; i++) {
    if (planks[i] != 0) {
        while (!stack.isEmpty() && planks[i] <= planks[stack.last()]) {
            stack.removeLast();
        }
        stack.addLast(i);
    }
}

We push start positions to stack (we just reuse end side of the queue as stack here). For each plank we remove all the planks from the top of the stack that wrap the current plank. If the plank at the top of the stack does not wrap the current plank, it is guaranteed that no other planks in the stack wrap the current plank because if there were such a plank, it would also wrap the plank at the top of the stack and thus would have been removed when the plank at the top was added to the stack. The total time complexity of the inner loop is linear because each plank is once added and once visited on the stack.

Now the stack contains only planks that are not wrapped by any other plank, and we store the remaining plank ends in a new array:

int[] ends = new int[planks.length];
while (!stack.isEmpty()) {
    int start = stack.removeLast();
    ends[start] = planks[start];
}

We also create two other helper arrays for plank starts and nail positions:

int[] starts = new int[ends.length];
for (int i = 1; i < ends.length; i++) {
    if (ends[i] > 0) {
        starts[ends[i]] = i;
    }
}

int[] nails = new int[starts.length];
for (int i = 0; i < C.length; i++) {
    if (nails[C[i]] == 0) {
        nails[C[i]] = i + 1;
    }
}

Now we traverse the ordered planks:

int result = -1;
Queue queue = new Queue(ends.length);
for (int i = 1; i < ends.length; i++) {
    if (ends[i] > 0) {
        if (!queue.isEmpty() && ends[queue.last()] == -1) {
             queue.removeLast();
        }
        ends[i] = -1;
        queue.addLast(i);
    } else if (queue.isEmpty()) {
        continue;
    }
    if (nails[i] != 0) {
        if (ends[queue.last()] == -1 || nails[i] < ends[queue.last()]) {
            ends[queue.last()] = nails[i];
            while (queue.size() > 1 && ends[queue.nextToLast()] > nails[i]) {
                queue.removeNextToLast();
            }
        }
    }
    if (starts[i] != 0) {
        int min = ends[queue.first()];
        if (min == -1) {
            return -1;
        }
        if (starts[i] == queue.first()) {
            queue.removeFirst();
        }
        if (result == -1 || min > result) {
            result = min;
        }
    }
}

We store plank starts on the queue and reuse ends array to store minimum nails for corresponding planks in the queue. For each nail we encounter during the iteration, we remove all planks from the queue for which minimum nail is larger than the current minimum nail, because if a plank is in the queue, then it means that it has started but not ended yet, and this nail can be used for that plank as well. The total time complexity of the inner while loop is linear because each element in the queue is added once and removed once.

The implementation of the Queue is straightforward:

private static class Queue {
    private int[] array;
    private int start = 0;
    private int end = -1;
    private int size = 0;

    Queue(int capacity) {
        this.array = new int[capacity];
    }
    void addLast(int element) {
        size++;
        end++;
        if (end == array.length) {
            end = 0;
        }
        array[end] = element;
    }
    int removeLast() {
        size--;
        int result = array[end--];
        if (end < 0) {
            end = array.length - 1;
        }
        return result;
    }
    int removeFirst() {
        size--;
        int result = array[start++];
        if (start == array.length) {
            start = 0;
        }
        return result;
    }
    int removeNextToLast() {
        size--;
        int index = nextToLastIndex();
        int result = array[index];
        array[index] = array[end];
        end = index;
        return result;
    }
    int last() {
        return array[end];
    }
    int first() {
        return array[start];
    }
    int nextToLast() {
        return array[nextToLastIndex()];
    }
    boolean isEmpty() {
        return size == 0;
    }
    int size() {
        return size;
    }
    int nextToLastIndex() {
        return end > 0 ? end - 1 : array.length - 1;
    }
}

So, the time complexity of the loops is either O(N) or O(M), and helper arrays and queues don't take more than 2*M space, so the overall time complexity is O(N+M) and space O(M).

The complete solution is available on the Codility test results page.