We have one 2D array, filled with zeros and ones. We have to find the starting point and ending point of all rectangles filled with 0. It is given that rectangles are separated and do not touch each other however they can touch the boundary of the array.A rectangle might contain only one element.
Examples:
input = [
[1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 0, 0, 0, 1],
[1, 0, 1, 0, 0, 0, 1],
[1, 0, 1, 1, 1, 1, 1],
[1, 0, 1, 0, 0, 0, 0],
[1, 1, 1, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1]
]
Output:
[
[2, 3, 3, 5], [3, 1, 5, 1], [5, 3, 6, 5]
]
Explanation:
We have three rectangles here, starting from
(2, 3), (3, 1), (5, 3)
Input = [
[1, 0, 1, 1, 1, 1, 1],
[1, 1, 0, 1, 1, 1, 1],
[1, 1, 1, 0, 0, 0, 1],
[1, 0, 1, 0, 0, 0, 1],
[1, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 1, 1],
[1, 1, 0, 1, 1, 1, 0]
]
Output:
[
[0, 1, 0, 1], [1, 2, 1, 2], [2, 3, 3, 5],
[3, 1, 4, 1], [5, 3, 5, 6], [7, 2, 7, 2],
[7, 6, 7, 6]
]
Step 1: Look for the 0 row-wise and column-wise
Step 2: When you encounter any 0, save its position in output array and using loop change all related 0 with this position in any common number so that we can exclude it from processing next time.
Step 3: When you change all related 0 in Step 2, store last processed 0’s location in output array in the same index.
Step 4: Take Special care when you touch the edge, by not subtracting -1 because the loop has broken on the exact location.
Below is the implementation of above approach:
Python3
# Python program to find all # rectangles filled with 0def findend(i,j,a,output,index): x = len(a) y = len(a[0]) # flag to check column edge case, # initializing with 0 flagc = 0 # flag to check row edge case, # initializing with 0 flagr = 0 for m in range(i,x): # loop breaks where first 1 encounters if a[m][j] == 1: flagr = 1 # set the flag break # pass because already processed if a[m][j] == 5: pass for n in range(j, y): # loop breaks where first 1 encounters if a[m][n] == 1: flagc = 1 # set the flag break # fill rectangle elements with any # number so that we can exclude # next time a[m][n] = 5 if flagr == 1: output[index].append( m-1) else: # when end point touch the boundary output[index].append(m) if flagc == 1: output[index].append(n-1) else: # when end point touch the boundary output[index].append(n) def get_rectangle_coordinates(a): # retrieving the column size of array size_of_array = len(a) # output array where we are going # to store our output output = [] # It will be used for storing start # and end location in the same index index = -1 for i in range(0,size_of_array): for j in range(0, len(a[0])): if a[i][j] == 0: # storing initial position # of rectangle output.append([i, j]) # will be used for the # last position index = index + 1 findend(i, j, a, output, index) print (output)# driver codetests = [ [1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 0, 0, 0, 1], [1, 0, 1, 0, 0, 0, 1], [1, 0, 1, 1, 1, 1, 1], [1, 0, 1, 0, 0, 0, 0], [1, 1, 1, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1, 1] ]get_rectangle_coordinates(tests) |
Output:
[[2, 3, 3, 5], [3, 1, 5, 1], [5, 3, 6, 5]]
Time Complexity: O(x*y).
Auxiliary Space: O(x*y).
Please refer complete article on Find all rectangles filled with 0 for more details!
You’ll access excellent video content by our CEO, Sandeep Jain, tackle common interview questions, and engage in real-time coding contests covering various DSA topics. We’re here to prepare you thoroughly for online assessments and interviews.
Ready to dive in? Explore our free demo content and join our DSA course, trusted by over 100,000 neveropen! Whether it’s DSA in C++, Java, Python, or JavaScript we’ve got you covered. Let’s embark on this exciting journey together!
