1

I have a three dimensional bit array A of dimension N x N x N. The question is to find a maximum volume cuboid in A, i.e. indices i1, i2, i3, j1, j2, j3, such that A(k1, k2, k3) = 1 for all i <= k <= j and volume = prod(j-i+1) is maximum.

The crucial claim is that I need complexity O(N^3) (up to logarithmical Term if necessary). Stating an algorithm for O(N^4) is easy. But the O(N^3) complexity seems to be a far harder problem. There are also many other discussions on exactly that problem online, unfortunately without a (correct) solution.

Thanks a lot for your appreciated help!

Best, Christian

P-almo Kristian
  • 11
  • In 2-D version the solution for $O(n^2) can be found here. Can you provide some links about discussions to this 3-D problem? – auntyellow Jul 23 '22 at 00:56
  • 1
    Yes, in the 2D case you can do it in O(N^2) and it is even a famous coding interview question. Unfortunately that approach seems no to extend to the 3D case. Here an older link to a wrong solution of the 3D case: https://stackoverflow.com/questions/9923601/find-largest-cuboid-containing-only-1s-in-an-nxnxn-binary-array – P-almo Kristian Jul 23 '22 at 07:27

0 Answers0