Find largest cuboid containing only 1's in an NxNxN binary array

Question

Given an NxNxN binary array (containing only 0's or 1's), how can we obtain the largest cuboid with a non-trivial solution i.e. in O(N^3) ?

--

It is the same problem that Find largest rectangle containing only zeros in an N×N binary matrix but in an upper dimension. Also, in my case, the largest rectangle can "cross the edge" of the array i.e. the space is like a torus for a 2D matrix.

For a 2D array, if the entry is :

00111
00111
11000
00000
00111

the solution depicted by 'X' is

00XXX
00XXX
11000
00000
00XXX

I've done the computation for a NxN binary array and find a solution for the largest rectangle problem in O(N^2) by following the idea in http://tech-queries.blogspot.de/2011/03/maximum-area-rectangle-in-histogram.html. But I don't know how to apply it for a 3D array.

--

Example for a 3x3x3 array where the solution "cross the edge":

111
100
011

111
001
111

011
110
011

the solution should be:

1XX
100
0XX

1XX
001
1XX

0XX
110
0XX

Answer 1

This solution has O(N³ log² N) complexity (may be optimized to O(N³ log N)). Additional integer array of size 2*8*N³ will be needed.

1. Compute r(i,j,k): for each of the N² rows, compute cumulative sum of all non-zero elements, resetting it when a zero element is found.
2. Perform the following steps for various values of K, using Golden section search (or Fibonacci search) to find the maximum result.
3. Compute c(i,j,k): for each of the N² columns, compute cumulative sum of all elements with r(i,j,k) >= K, resetting it when an element with r(i,j,k) < K is found. For good visualization of steps 1 and 2, see this answer.
4. Perform the last step for various values of M, using Golden section search to find the maximum result.
5. Compute sum: for each of the N² values of 3rd coordinate, compute cumulative sum of all elements with c(i,j,k) >= M, resetting it when an element with c(i,j,k) < M is found. Calculate sumKM and update the best so far result if necessary.

"cross the edge" property of the array is handled in obvious way: iterate every index twice and keep all cumulative sums not larger than N.

For multidimensional case, this algorithm has O(N^D log^D-1 N) time complexity and O(D*N^D) space complexity.

---

Optimization to O(N³ log N)

Step 4 of the algorithm sets a global value for M. This step may be excluded (and complexity decreased by log N) if value for M is determined locally.

To do this, step 5 should be improved. It should maintain a double-ended queue (head of which contains local value of M) and a stack (keeping starting positions for all values of M, evicted from the queue).

While c(i,j,k) increases, it is appended to the tail of the queue.

If c(i,j,k) decreases, all larger values are removed from the queue's tail. If it decreases further (queue is empty), stack is used to restore 'sum' value and put corresponding 'M' value to the queue.

Then several elements may be removed from the head of the queue (and pushed to the stack) if this allows to increase local solution's value.

For multidimensional case, this optimization gives O(N^D log^D-2 N) complexity.

Answer 2

Here is only O(N^4).

Lets assume you are storing cubiod in bool cuboid[N][N][N];

bool array2d[N][N];

for(int x_min = 0; x_min < N; x_min++) {
   //initializing array2d
   for(int y = 0; y < N; y++) {
      for(int z = 0; z < N; z++) {
         array2d[y][z] = true;
      }
   }

   //computation
   for(int x_max = x_min; x_max < N; x_max++) {
      // now we want to find largest cube that
      // X coordinates are equal to x_min and x_max

      // cells at y,z can be used in cube if and only if
      // there are only 1's in cuboid[x][y][z] where x_min <= x <= x_max

      // so lets compute for each cell in array2d,
      // if are only 1's in cuboid[x][y][z] where x_min <= x <= x_max
      for(int y = 0; y < N; y++) {
         for(int z = 0; z < N; z++) {
            array2d[y][z] &= cubiod[x_max][y][z];
         }
      }

      //you already know how to find largest rectangle in 2d in O(N^2)
      local_volume = (x_max - x_min + 1) * find_largest_area(array2d);

      largest_volume = max(largest_volumne, local_volume);
   }
}

You can use the same trick, to compute best solution in X dimentions. Just reduce the problem to X-1 dimensions. Complexity: O(N^(2*X-2)).