L-Shaped Plots Kickstart Problem
Task:- Given a matrix of ‘R’ rows and ‘C’ columns with every element either 1 or 0, we have to find the different number of valid L-shaped plots. Conditions for L-shaped plot to be valid are :
- Each box/element for the L-shape should be 1.
- The length of L should be 2 times the breadth(b).
- Length and breadth >= 2.
See sample test cases in the question for a clear understanding.
Brute Force Approach:- We can visit every index i,j of the matrix and check if it is 1. If it is, then we traverse in up, down, left, and right directions to find the number of consecutive 1s in each direction and try to see how many L-shaped plots we can make which are valid.
We can calculate the number of valid L-shaped plots for each possible (length, breadth) pair.
Consider for a given plot at i, j with value 1 has ->
Consecutive no of 1s in the up direction ( up ) = 7
Consecutive no of 1s in the down direction ( down ) = 2
Consecutive no of 1s in the left direction ( left ) = 7
Consecutive no of 1s in the right direction ( right ) = 3.
The total no of valid L-shaped possible for pair of (up, right) -> (length, breadth) are 2 as shown in the image below:
The total no of valid L-shaped possible for pair of (up, left) -> (length, breadth) are 4 as shown in the image below:
Thus for every index i&j, we calculate noOfLs = getLs(up,left) + getLs(up,right) + getLs(down,left) + getLs(down,right)
Where getLs function gives no of L-shaped plots that can be formed from that particular pair.
For a given (length, breadth) :
Number of Ls = max(0, min( length, breadth/2 ) + max(0, min(length/2, breadth))
The first term gives all the Ls highlighted in black color & the second term gives all the Ls highlighted in red color.
The time complexity of this approach would be O(R*C(R+C)) or simple O(N³) if R and C are equal. This is because, for each element in the matrix, we calculate the consecutive number of 1s in each direction by traversing in that direction.
Total no of elements -> R*C , Calculate consecutive 1s in each direction -> O(R + R + C + C) -> O(R+C).
Overall time complexity becomes O(R*C(R+C)).
Efficient Approach:- We can pre-process the matrix and store the consecutive number of 1s for each (i, j) index by using the idea of prefix sum approach. After this pre-processing, we will have 4 matrices up, down, left, and right all with R*C elements. Each element in the prefix sum will store the consecutive number of 1s in that particular direction at that particular index pair of (i, j).
Then we can do the same thing that we did in the brute force approach i.e — to get all possible valid L-shaped plots from a consecutive number of 1s in each direction.
The time complexity of this approach is O(R*C) or o(N²) if R and C are equal. This is because we pre-process the matrix in O(R*C) time complexity and then for each element in the matrix, we get the consecutive number of 1s in each direction in constant time ( O(1) ) by doing a lookup in the prefix sum arrays.
Efficient code:-
Similar problems that you might like:-
