How to use Binary Search In Javascript
In this approach, we are using binary search to find the largest square size in the matrix. By iteratively narrowing down the search space between the minimum and maximum possible square sizes, we determine the largest valid square size by checking if each potential square’s elements are all ones.
Example: The below example uses Binary Search to find the Largest square formed in a matrix using JavaScript.
let mat = [
[1, 1, 1, 1],
[1, 1, 1, 1],
[1, 1, 1, 1],
];
let n = mat.length;
let m = mat[0].length;
let res = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
if (mat[i][j] === 1) {
let low = 1;
let high =
Math.min(n - i, m - j);
while (low <= high) {
let mid = Math.
floor((low + high) / 2);
let valSquare = true;
for (let k = 0; k < mid; k++) {
for (let l = 0; l < mid; l++) {
if (mat[i + k][j + l] === 0) {
valSquare = false;
break;
}
}
if (!valSquare) break;
}
if (valSquare) {
res = Math.max(res, mid);
low = mid + 1;
} else {
high = mid - 1;
}
}
}
}
}
console.log(res);
Output
3
Time Complexity: O(n * m * log(min(n, m))), where, n is number of rows and m is number of columns.
Space Complexity: O(1)
Largest Square Formed in a Matrix using JavaScript
Given a matrix, our task is to find the largest square formed in a matrix using JavaScript. The largest square is a square that contains the same number of rows and columns and no more squares can be possible to form in that matrix that contains more rows and columns than this square.
The below methods can be implemented to accomplish the task.
Table of Content
- Using Dynamic Programming
- Using Binary Search
Contact Us