Facebook Interview Question SDE1s
Country: United States
Simple brute-force solution with O(N^2*M^2) where N and M are matrix width and height, but O(1) memory complexity:
private static boolean isRectangle(byte[][] m) {
int h=m.length,w=m[0].length;
for(int y1=0;y1<h;y1++)
for(int x1=0;x1<w;x1++)
if(m[y1][x1]==1)
for(int y2=y1+1;y2<h;y2++)
for(int x2=x1+1;x2<w;x2++)
if(m[y1][x2]==1 && m[y2][x1]==1 && m[y2][x2]==1)
return true;
return false;
}
private static void doTest1Yes() {
byte[][] m = {
{1,0,0,1,0},
{0,0,1,0,1},
{0,0,0,1,0},
{1,0,1,0,1}};
System.out.println(isRectangle(m)?"YES":"NO");
}
private static void doTest2No() {
byte[][] m = {
{1,0,0,1,0},
{0,0,0,0,1},
{0,0,0,1,0},
{1,0,1,0,1}};
System.out.println(isRectangle(m)?"YES":"NO");
}
public static void main(String[] args) {
doTest1Yes();
doTest2No();
}
More efficient solution be time possible, but it will require additional memory, so this one also have chance to exists.
Much more efficient solution is to store only 1-th cells somewhere and then review only them looking for rectangle. Also we can notice that to make up a rectangle we need to have 2 pairs of points with same x or y coordinate, so let's store them grouped by y or x coordinate. Finally we should not check individually each pair or lines in matrix, we can just intersect sets of points in each line to see if final intersection will have 2 or more points.
Store all 1-th cells into a map take O(N*M), where N and M are matrix width and heigh, then we enumerate all pairs of lines/columns (it can be O(N^2) or O(M^2) what is less) and then make intersection of two sets, that takes O(N) or O(M) time. Lets assume that total it will be O(N*M+N^2*M) or (ON*M+M^2*N) - we can choose smaller dimension to have smaller from those two. Additional space needed is O(K) where K - number of 1-th in matrix. Code:
private static boolean isRectangle(byte[][] m) {
Map<Integer, Set<Integer>> yPoints = new HashMap<Integer, Set<Integer>>();
int h=m.length,w=m[0].length;
for(int y=0;y<h;y++)
for(int x=0;x<w;x++)
if(m[y][x]==1)
yPoints.computeIfAbsent(y,s->new HashSet<Integer>()).add(x);
List<Map.Entry<Integer, Set<Integer>>> lines =
new ArrayList<Map.Entry<Integer, Set<Integer>>>(yPoints.entrySet());
for(int i=0;i<lines.size();i++)
for(int j=i+1;j<lines.size();j++) {
Set<Integer> points = new HashSet<Integer>(lines.get(i).getValue());
points.retainAll(lines.get(j).getValue());
if(points.size()>=2) return true;
}
return false;
}
private static void doTest1Yes() {
byte[][] m = {
{1,0,0,1,0},
{0,0,1,0,1},
{0,0,0,1,0},
{1,0,1,0,1}};
System.out.println(isRectangle(m)?"YES":"NO");
}
private static void doTest2No() {
byte[][] m = {
{1,0,0,1,0},
{0,0,0,0,1},
{0,0,0,1,0},
{1,0,1,0,1}};
System.out.println(isRectangle(m)?"YES":"NO");
}
public static void main(String[] args) {
doTest1Yes();
doTest2No();
}
public static void main(String[] args){
int[][] arr = {{1, 0, 0, 1, 0}, {0, 0, 1, 0, 1}, {0, 0, 0, 1, 0}, {1, 0, 1, 0, 1}};
rectangles(arr);
}
public static void rectangles(int[][] arr){
int n = arr.length;
int m = arr[0].length;
for(int i = 0; i < n; i++){
int index1 = -1;
int index2 = -1;
for(int j = 0; j < m; j++){
if(arr[i][j] == 1 && index1 == -1)
index1 = j;
else if(arr[i][j] == 1 && index2 == -1)
index2 = j;
if(index1 != -1 && index2 != -1){
check(arr, i, index1, i, index2);
index1 = index2;
index2 = -1;
}
}
}
}
public static void check(int[][] arr, int i1, int j1, int i2, int j2){
int n = arr.length;
int m = arr[0].length;
for(int i = i1+1; i < n; i++){
int[] row = arr[i];
if(row[j1] == 1 && row[j2] == 1){
System.out.println("Corner 1 - " + i1 + ", " + j1);
System.out.println("Corner 2 - " + i1 + ", " + j2);
System.out.println("Corner 3 - " + i + ", " + j1);
System.out.println("Corner 4 - " + i + ", " + j2);
System.out.println();
}
}
}
@Alex came up with a cool idea in an other thread to solve this kind of question in O(n*m^2):
- scan from top to down, line by line
- for each line, remember each combination of 2 1's and push that into a hash-set
- if you ever find that combination again in a later line, you get your rectangle
I think the solution has a lot of charm, especially it's a sparse matrix
Find the 3 corners and calculate the last one
public static bool IsThereRectangle(int[,] a)
{
int n = a.GetLength(0);
int m = a.GetLength(1);
if (a[0, 0] == 1 && a[n - 1, m - 1] == 1 && a[0, m - 1] == 1 && a[n - 1, 0] == 1)
{
return true;
}
for (int i = 0; i < n; i++){
int temp = i;
for (int j = 0; j < m; j++)
{
if (a[i, j] == 1)
{
int c1 = j;
while (++j < m)
{
int tmp = i;
if (a[i, j] == 1)
{
while (++i < n)
{
if (a[i, j] == 1)
{
if (a[i, c1] == 1)
{
return true;
}
}
}
}
i = tmp;
}
}
}
i = temp;
}
return false;
}
public static bool IsThereRectangle(int[,] a)
{
int n = a.GetLength(0);
int m = a.GetLength(1);
if (a[0, 0] == 1 && a[n - 1, m - 1] == 1 && a[0, m - 1] == 1 && a[n - 1, 0] == 1)
{
return true;
}
for (int i = 0; i < n; i++){
int temp = i;
for (int j = 0; j < m; j++)
{
if (a[i, j] == 1)
{
int c1 = j;
while (++j < m)
{
int tmp = i;
if (a[i, j] == 1)
{
while (++i < n)
{
if (a[i, j] == 1)
{
if (a[i, c1] == 1)
{
return true;
}
}
}
}
i = tmp;
}
}
}
i = temp;
}
return false;
}
Found the brute force O(N^2 M^2) solution, and was able to find the O(N^2 M) one. The bitwise solution for the N, M < 32 case is pretty awesome!
Implementation in JavaScript.
function intersect(setA, setB){
const intersection = new Set();
setA.forEach((item) => {
if (setB.has(item)){
intersection.add(item);
}
});
return intersection;
}
function hasRect(matrix){
const N = matrix.length;
const M = matrix[0].length;
const H = new Map();
for (let i = 0; i < N; i++){
for (let j = 0; j < M; j++){
if (matrix[i][j] === 1){
if (!H.has(i)){
H.set(i, new Set());
}
const columns = H.get(i);
columns.add(j);
}
}
}
for (let i = 0; i < N; i++){
for (let j = i + 1; j < N; j++){
const firstColumn = H.get(i);
const secondColumn = H.get(j);
const intersection = intersect(firstColumn, secondColumn);
if (intersection.size >= 2){
const intersectionArray = Array.from(intersection);
console.log(`Top Left (${i}, ${intersectionArray[0]})`);
console.log(`Top Right (${i}, ${intersectionArray[1]})`);
console.log(`Bottom Left (${j}, ${intersectionArray[0]})`);
console.log(`Bottom Right (${j}, ${intersectionArray[1]})`);
return true;
}
}
}
return false;
}
const matrix = [
[1, 0, 0, 1, 0],
[0, 0, 1, 0, 1],
[0, 0, 0, 1, 0],
[1, 0, 1, 0, 1]
];
console.log(hasRect(matrix));
Based on ChrisK's idea :
bool isRectangle( const vector<vector<int>>& matrix )
{
int rows = matrix.size();
if(rows == 0 ) return false;
int columns = matrix[0].size();
unordered_map<int, unordered_set<int>> table;
for( int i=0; i<rows; ++i)
{
for( int j=0; j<columns-1; ++j)
{
for(int k=j+1; k<columns; ++k)
{
if( matrix[i][j]==1 && matrix[i][k]==1)
{
if( table.find(j) != table.end() && table[j].find(k) != table[j].end() )
{
return true;
}
if( table.find(k) != table.end() && table[k].find(j) != table[k].end() )
{
return true;
}
table[j].insert(k);
table[k].insert(j);
}
}
}
}
return false;
}
It can be done in o(m*n*(max(m,n)))
you basically need to check whether the top left corner can make a square.
public static void main(String[] args) {
boolean[][] m = new boolean[][]{
{true, false, false, true, false},
{false, false, true, false, true},
{false, false, false, true, false},
{true, false, true, false, true}
};
System.out.println(hasRectangleInMatrix(m));
}
static boolean hasRectangleInMatrix(boolean[][] matrix) {
for (int row = 0; row < matrix.length; row++) {
for (int col = 0; col < matrix[0].length; col++) {
if (matrix[row][col] && canFormTriangle(matrix, row, col)) {
return true;
}
}
}
return false;
}
static boolean canFormTriangle(boolean[][] matrix, int leftRow, int leftCol) {
int maxSize = Math.min(matrix.length - leftRow, matrix[0].length - leftCol);
while (maxSize > 1) {
if (matrix[leftRow + maxSize - 1][leftCol] && matrix[leftRow + maxSize - 1][leftCol + maxSize - 1] && matrix[leftRow][leftCol + maxSize - 1]) {
System.out.println("top left corner at: (" + leftRow + "," + leftCol + ")" + " with Size: " + maxSize);
return true;
}
maxSize--;
}
return false;
}
def find_rect(maze):
# print maze
rows = len(maze)
cols = len(maze[0])
sq_len = min(rows, cols)
if not sq_len%2==0:
sq_len = sq_len-1
all_ones = []
for i in range(0, rows):
for j in range(0, cols):
if maze[i][j]==1:
all_ones.append((i,j))
# print all_ones
rects = []
small_maze = []
for (x,y) in all_ones:
for inc in range(1, sq_len):
if ((x,y+inc)in all_ones) and ((x+inc,y+inc) in all_ones) and ((x+inc,y) in all_ones):
for i in range(x, x+inc+1):
for j in range(y, y+inc+1):
small_maze.append(maze[i][j])
print small_maze
static String isRectangle(int[][] arr) {
int row = 0;
int col = 0;
int result = 0;
while(row < arr.length - 2) {
if(arr[row][col] == 1 && arr[row + 2][col+2] == 1 && arr[row + 2][col] == 1 && arr[row][col+2] == 1) {
return "YES";
}
row++;
}
row = 0;
while(col < arr.length - 2) {
if(arr[row][col] == 1 && arr[row + 2][col+2] == 1 && arr[row + 2][col] == 1 && arr[row][col+2] == 1) {
return "YES";
}
col++;
}
return "NO";
}
static String isRectangle(int[][] arr) {
int row = 0;
int col = 0;
int result = 0;
while(row < arr.length - 2) {
if(arr[row][col] == 1 && arr[row + 2][col+2] == 1 && arr[row + 2][col] == 1 && arr[row][col+2] == 1) {
return "YES";
}
row++;
}
row = 0;
while(col < arr.length - 2) {
if(arr[row][col] == 1 && arr[row + 2][col+2] == 1 && arr[row + 2][col] == 1 && arr[row][col+2] == 1) {
return "YES";
}
col++;
}
return "NO";
}
static String isRectangle(int[][] arr) {
int row = 0;
int col = 0;
int result = 0;
while(row < arr.length - 2) {
if(arr[row][col] == 1 && arr[row + 2][col+2] == 1 && arr[row + 2][col] == 1 && arr[row][col+2] == 1) {
return "YES";
}
row++;
}
row = 0;
while(col < arr.length - 2) {
if(arr[row][col] == 1 && arr[row + 2][col+2] == 1 && arr[row + 2][col] == 1 && arr[row][col+2] == 1) {
return "YES";
}
col++;
}
return "NO";
}
public class CheckMatrix {
public static void main(String[] args) {
int m[][]= {{1, 0, 0, 1, 0},
{0, 0, 1, 0, 1},
{0, 0, 0, 1, 0},
{1, 0, 1, 0, 1}};
System.out.println(checkInternal(m,0,0,2));
}
private static boolean checkInternal(int[][] m, int dx,int dy,int s) {
if(m[dy][dx] == 1 && m[dy][dx+s] == 1 && m[dy+s][dx] == 1 && m[dy+s][dx+s] == 1) return true;
if(dx+s == m[dy].length -1) {
dx=0;
if(dy+s == m.length -1) {
dy=0;
if(s == m.length -1) {
return false;
}
else s ++;
} else {
dy++;
}
} dx++;
return checkInternal(m,dx,dy,s);
}
}
class matrix
{
public static int RectCount = 0;
public static void Main(String [] args)
{
int[,] matrix = new int[4, 5] { { 1, 0, 0, 1, 0 }, { 0, 0, 1, 0, 1 }, { 0, 0, 0, 1, 0 }, { 1, 0, 1, 0, 1 } };
CountRectangles(matrix, 0);
Console.WriteLine(RectCount);
Console.ReadLine();
}
private static void CountRectangles(int[,] matrix, int dimensionX)
{
int iid = -1;
Stack s = new Stack();
if (dimensionX >= matrix.GetLength(0))
return;
for(int j =0;j<matrix.GetLength(1);j++)
{
if (matrix[dimensionX, j] == 1)
s.Push(j);
}
outer: while(s.Count>0)
{
int jid = Convert.ToInt32(s.Pop());
if (iid == -1)
{
for (int i = dimensionX+1; i < matrix.GetLength(0); i++)
{
if (matrix[i, jid] == 1)
{
iid = i;
goto outer;
}
}
}
else
{
if (matrix[iid, jid] == 1)
RectCount++;
}
}
CountRectangles(matrix, dimensionX + 1);
}
}
There is a O(N^3) solution. In this case, the only thing that we need to know is, if there is more than one line such that the column j and column j + dist have the value 1.
So, for each line we find the pairs of 1's and increment in a auxiliary O(N^2) memory the position (j, j + dist), if you increment a position that already has the value 1, then the answer is YES.
So the final complexity is O(N^3) to find the pairs of 1's in each line. O(N^2) of space. Note that, this solution is general and doesn't assume that the value of N < 32 or N < 64.
def is_rectangle?(matrix)
unos = {}
for i in 0...matrix.size
for j in 0...matrix.first.size
if matrix[i][j] == 1
if !ones[j].nil?
ones[j].each do |fila|
side = i - fila
if matrix[i][j + side] == 1 && matrix[fila][j + side] == 1
return true
end
end
ones[j] << i
else
ones[j] = [i]
end
end
end
end
return false
end
matrix1 = [
[1,0,0,1,0],
[0,0,1,0,1],
[0,0,0,1,0],
[1,0,1,0,1]
]
matrix2 = [
[1,0,0,1,0],
[1,0,1,0,1],
[0,0,0,1,0],
[1,0,0,0,1]
]
matrix3 = [
[1,0,0,1,0],
[1,1,0,1,1],
[0,0,0,1,0],
[1,1,0,1,1]
]
#true
puts is_rectangle?(matrix1)
#false
puts is_rectangle?(matrix2)
#true
puts is_rectangle?(matrix3)
We can get O(Min(m,n)^2) if we do bit manipulation:
- incarose November 14, 2017For each row ( or column depends M < N or N < M ) we do
( example with rows )
Ri & Rj = Rij
if Rij > 0 menas we have 1's at the same Col.
Now lets check if the number of 1's > 1
if (Rij and (Rij -1)) > 0 ( x & (x-1) removes the right most 1')
we have more than 1 '1' in the row. And we found a rectangle.
This will need a nested loop to check every Ri & Rj ( i< j ) i,j <= Number of rows ( or columns )