Quick note: feel free to answer in any language of choice
I want to quickly and efficiently search a 2D array for the first valid location to place an object. For a location to be considered valid it means that the object of specified height and width will fit in an area marked with only 0s. For this case you can imagine the object we specify has a height and width > 1 and there will exist a valid location in the 2d array. For example, imagine I have the following 2D array
[
[0,0,0,0,0,0,1],
[0,1,0,0,0,1,0],
[0,0,0,1,0,0,0],
[0,1,0,0,0,0,0],
[0,0,0,0,0,0,0],
[0,0,0,0,0,0,0],
[0,0,0,0,0,0,0]
]
And an object with height 3 and width 3, the function should return An object with the following row and column as the first valid location {row: 2, col:4}. First valid location refers to the top left corner where an object of unknown height and width can fit onto the 2D array and cover an area where every element is a 0.
Also maybe the best we can do is n*m and have to search every element. I just have wishful thinking that there are areas I can skip over since I know they won’t work. Using the example above I tried searching starting from the width of object. In this case I would begin my search from (0,2). I would search down to (2,2) before moving over to the left and searching there. Once I find a collision at (1,1) I know I do not have to search (0,0) or (1,0). What I want to solve are the following two points:
my thought process has been some sort of bfs/dfs algorithm, but I run into problems where I check areas that I know aren’t valid. I need a way to efficiently know what isn’t valid to avoid spending time on those areas
I would go with the following: For each row setup an array of "zero" (valid) positions with its lenght. lets call it [pos,len]
0 [0,6]
1 [0,1],[2,3],[6,1]
2 [0,3],[4,3]
3 [0,1],[2,5]
4 [0,7]
5 [0,7]
6 [0,7]
When you are looking for a rectangle of 3,3 you are left with
1 [2,3]
2 [0,3],[4,3]
3 [2,5]
4 [0,7]
5 [0,7]
6 [0,7]
As you want a height of (3,3), rows should have the correct overlap in postions with lenght. starting with row1 [2,3]. do we have in row2 [0,3] an overlap where:
pos2 + len2 - pos1 >=3 and pos1 + len1 - pos2 => 3
this would give us 0 + 3 - 2 >= 3 and 2 + 3 - 0 => 3 FALSE
now we can take the next in row2 [4,3] what gives us another FALSE
time to forget about row1 and move to row2[0,3] compared to row3 [2,5]
etc, etc.
When yo have 2 times TRUE, you have found your position. 2 as it is the rectangle height (3) -1