1

Given a 2D array only has 1s and 0s. 1 means there is a point and return false if there is no rectangle in this array. For example, 

int [] [] array = { {1,0,0,0,1},
                    {1,0,1,0,1},
                    {0,1,1,0,1} }

return true

int [] [] array = { {1,0,0,0,1},
                    {1,0,1,0,0},
                    {0,1,1,0,1} }

return false

I came up with a O(n^3) solution, but I was wondering that is there any method can do better?

Thanks!

EmilioPelaez
  • 18,758
  • 6
  • 46
  • 50
Shuishui
  • 61
  • 1
  • 3
  • 4
    Why not post your O(n^3) solution to codereview.stackexchange.com? – Attilio Apr 02 '15 at 18:22
  • Are there any limits to the size of the matrix? – 200_success Apr 02 '15 at 18:34
  • What you're looking for is a pair of rows r1 and r2 such that the bitwise AND of both rows has at least two bits, i.e. bits(r1 & r2) > 1. Using actual bits instead of integer strings could help to optimize, but doesn't actually improve the algorithmic complexity. It is a very similar problem to Bit-Matrix Multiplication, for which there is a sub O(n^3) solution (deemed the four-russians method) that pre-computes sub-problems, so it may help to look at that: http://theory.stanford.edu/~virgi/cs367/lecture2.pdf – Alfredo Gimenez Apr 02 '15 at 18:37
  • isn't this a duplicate of http://stackoverflow.com/questions/2478447 ? – tigrou Apr 02 '15 at 21:51

0 Answers0