LeetCode - 1992. Find All Groups of Farmland
Approach
- WE FIRST CREATE A FARMER FUNCTION THAT WE WILL CALL RECURSIVELY
- IT WILL CHECK IF THE LAND WE ARE TRYING TO ACCESS IS OUT OF BOUNDS OR IS NOT A FIELD IN WHICH CASE IT WILL JUST RETURN BACK
- ONCE WE HAVE A FIELD THAT IS IN BOUNDS AND NOT ZERO
- WE MARK IT ZERO TO KNOW THAT WE HAVE ALREADY VISITED THIS POINT AND NEED NOT CONSIDER IT AGAIN
- NOW IN OUR ARRAY CONTAINING THE LEFT MOST POINTS AND RIGHT MOST POINTS
- INITIALLY THE POINT IN LAND THAT WE FIRST ENCOUNTER A FIELD LEFT MOST AND RIGHT MOST POINTS ARE ITSELF ONLY
- NOW IN THE RECURSIVE FUNCTION WE COMPARE OUR FIELD COORDINATED TO THE MIN AND MAX OF THE ORIGINAL COORDINATES AND MODIFY THEM ACCORDINGLY
- LEFT MOST POINT WILL BE THE LEAST POSSIBLE COORDINATE
- RIGHT MOST POINT WILL BE THE MAX POSSIBLE COORDINTE
- JUST RETURN THE OUTPUT ARRAY
/**
* @param {number[][]} land
* @return {number[][]}
*/
var findFarmland = function (land) {
let rows = land.length;
let cols = land[0].length;
let endRow = 0;
let endCol = 0;
let result = [];
callDFS = (i, j) => {
if (i < 0 || j < 0 || i >= rows || j >= cols || land[i][j] == 0) {
return;
}
endRow = Math.max(endRow, i);
endCol = Math.max(endCol, j);
land[i][j] = 0;
callDFS(i + 1, j);
callDFS(i - 1, j);
callDFS(i, j + 1);
callDFS(i, j - 1);
}
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (land[i][j] === 1) {
endRow = 0;
endCol = 0;
// call recursion
callDFS(i, j);
result.push([i, j, endRow, endCol]);
}
}
}
return result;
};
console.log(findFarmland([[1, 0, 0], [0, 1, 1], [0, 1, 1]]))
Top comments (0)