|
//Traditional Approach |
|
|
|
var construct = function(grid) { |
|
return helper(grid, 0, 0, grid.length); |
|
}; |
|
function helper(grid, i, j, w) { |
|
if (allSame(grid, i, j, w)) |
|
return new Node(grid[i][j] === 1 ? true : false, true); |
|
const halfW = Math.floor(w / 2); |
|
let node = new Node(true, false); |
|
node.topLeft = helper(grid, i, j, halfW); |
|
node.topRight = helper(grid, i, j + halfW, halfW); |
|
node.bottomLeft = helper(grid, i + halfW, j, halfW); |
|
node.bottomRight = helper(grid, i + halfW, j + halfW, halfW); |
|
return node; |
|
} |
|
|
|
function allSame(grid, i, j, w) { |
|
const val = grid[i][j]; |
|
for (let x = i; x < i + w; x++) { |
|
for (let y = j; y < j + w; y++) { |
|
if (grid[x][y] !== val) { |
|
return false; |
|
} |
|
} |
|
} |
|
return true; |
|
} |
|
|
|
|
|
|
|
|
|
//Optimized Approach |
|
|
|
var construct = function(grid) { |
|
const checkQuadrant = (y1, x1, y2, x2) => { |
|
if(x2-x1 === 1) { |
|
return new Node(grid[y1][x1], 1, null, null, null, null) |
|
} |
|
for(let i = y1; i < y2; i++) { |
|
for(let j = x1; j < x2; j++) { |
|
if(grid[i][j] !== grid[y1][x1]) { |
|
const size = (x2-x1)/2 |
|
return new Node(1,0, |
|
checkQuadrant(y1, x1, y1+size, x1+size), |
|
checkQuadrant(y1, x1+size, y1+size, x2), |
|
checkQuadrant(y1+size, x1, y2, x1+size), |
|
checkQuadrant(y1+size, x1+size, y2, x2) |
|
) |
|
} |
|
} |
|
} |
|
return new Node(grid[y1][x1], 1, null, null, null, null) |
|
} |
|
return checkQuadrant(0,0,grid.length,grid.length) |
|
}; |
|
|
|
|
|
|
|
|
|
//Provide your comparison here. |