Not required for getting all the point on this exercise, but memory could have been reduced down to O(min{m,n}).
More precisely, we could have implemented an O(n) memory solution based on a row by row computation resting on a sort of union/find.