-
Notifications
You must be signed in to change notification settings - Fork 0
/
floorFill.js
71 lines (51 loc) · 2.68 KB
/
floorFill.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/*
Optimze Attempt
Time Complexity = O(R * C) - Because we have to g through over rows and columns;
Space Complexity = O(R * C) - Space Complexity should be constant because we are not using and space in this approach
*/
function floodFill(image,sc,sr,color){
//As we can set the source as starting most node //
let startingPoint = image[sr][sc];
//As the condition if the color is same we ignore //
if(startingPoint === color) return;
//Rows length as we need that for handling out of bound errors in recursion//
let rows = image.length;
//Columns length as we need that for handling out of bound errors in recursion//
let columns = image[0].length;
//Start Going Deep :-D into BlackHole but with base cases :-D
depth(image,sr,rows,sc,columns,color,startingPoint);
return image;
}
function depth(image,sr,rows,sc,columns,color,startingPoint){
//Boundary Cases//
if(sc < 0 || sc >= columns || sr < 0 || sr >= rows) return;
if(startingPoint !== image[sr][sc]) return
//Replacing the color with actual one we need//
image[sr][sc] = color;
//Recursive call For Top//
depth(image,sr-1,rows,sc,columns,color,startingPoint);
//Recursive call For Bottom//
depth(image,sr+1,rows,sc,columns,color,startingPoint);
//Recursive call For Left//
depth(image,sr,rows,sc-1,columns,color,startingPoint);
//Recursive call For Right//
depth(image,sr,rows,sc+1,columns,color,startingPoint);
}
// let image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
// console.log(floodFill(image,sc,sr,color))
/*
Steps For Optimized Solution
1 - We pick starting point and check if color is euqals to this then we should return the image.
2 - We have to save the length of rows we need that for handling out of bound errors in recursion.
3 - We have to save the length of columns we need that for handling out of bound errors in recursion.
4 - We now start our recursion ( Depth ) and pass all the aurguments starting point , image , color , sr = startingRow ,sc = startingColumn ,rows = no of rows , columns = no of columns//
6 - We now define base cases for recursion
If sr = startingRow , we are looking at is less then 0
OR sc = startingColumn , we are looking at is less then 0
OR sr = startingRow , is greater then equals to the length of rows
OR sc = startingColumn , is greater then equals to the length of columns
IF image[sr][sc] of that point is not equals to the startingPoint in recursion we should return.
If these are the cases are true any of them we should return.
5 - ELSE = Add color on that specific point i.e image[sr][sc] = color.
6 - Do recursive calls for top , bottom , right left.
**/