Linear time algorithm for slicing stacked boxes

Question

I have a problem which has a rather limited time constraint, and would like to see if I could get a nudge in the right direction.

Here is the problem:

You are presented with a wall with columns of different heights. Each column heights is represented as a non-zero integers.

Input state is defined using an array H of length N, containing heights of each of the N columns on the screen, for example:

Slicing the snapshot at a given height leaves a number of solid pieces above that height. E.g. slicing at level 2 would cut 3 solid pieces:

Slicing at level 1 would also cut 3 solid pieces:

Similarly, slicing at level 0 would return a single (one) solid piece, while slicing at level 3 wouldn't cut any pieces.

Requirement: Given an array of slice heights S of length M, containing all levels at which a "slice" should be performed, return an array of length M containing numbers of cut pieces for each respective cut.

For example, given the input H = {2, 1, 3, 2, 3, 1, 1, 2} and S = { 0, 1, 2, 3 }, the program should return quantities {1, 3, 3, 0}, according to the examples above.

Both N and M are in the range of around 20,000, but heights in each array can reach up to 1,000,000.

Both time and space worst-case complexity for the solution cannot exceed O(N + M + max(M) + max(N)).

The last constraint is what puzzles me: it basically means that I cannot have any nested for-loops, and I cannot seem to escape this.

Obviously, there is some clever preprocessing which needs to be done to yield final results in O(1) per slice, but I haven't been able to come up with it.

I went on to create an array of cut numbers for each slice level, and then update all of them as I iterate through H, but this turns out to be O(N*M), since I need to update all lower height levels.

Is there a data structure which would be appropriate for this task?

Answer 1

For each piece at a height there must be two edges intersecting that height, and by the definition of a "piece", the members of the set of such edges must all be distinct. So the number of pieces is half the number of edges in the set.

Further, the number of edges intersecting a specific height is the number of edges that have started below or at that height, minus the number of edges that have finished below or at it.

As such, we can calculate the number of pieces this way:

• Create an array Accumulator of size max(S) filled with zeroes.
• Iterate over H, and for each vertical edge you encounter add a +1 at the index i in Accumulator corresponding to the height of the edge's lower end, and add a -1 at the index j at corresponding to the edge's upper end. We're counting "ground level" as zero. Make sure to include the leading and trailing edges!
• Iterate over Accumulator and insert in each cell the sum of all cells up to and including it (O(max(S)) time if you keep a running sum)
• Divide every value in Accumulator by 2 to get the number of pieces at each height.
• Read out the number of pieces corresponding to the heights in S.

Example:

The edge's endpoints, from left to right, are

0,2
1,2
1,3
2,3
2,3
1,3
1,3
0,3

So our Accumulator array looks like this:

{2, 4, 0, -6}

Which after the accumulation step, looks like this:

{2, 6, 6, 0}

Which means the part counts are

{1, 3, 3, 0} 

As a warning, I've just come up with this on the spot, so while it feels correct I've no proof whether it actually is. Encouragingly, it worked on a few other token examples I tried as well.

Answer 2

Step 1: Maintain 3 column list (height, index_start, index_end)
Step 2: Sort the list according to height as primary key (decreasing), index_start as secondary key
Step 3: Let h be the highest height
Step 4: Merge all columns at height at least h and contiguous block
Step 5: Resulting number of blocks is blocks at height h
Step 6: h=h-1
Step 7: Go to step 4

This is the rough algo. Effectively the complexity is O(nlogn)