I came across this problem and solution at: http://www.geeksforgeeks.org/find-the-largest-rectangle-of-1s-with-swapping-of-columns-allowed/
But I couldn't get my head around the solution provided. Can someone please explain as to how the solution works ?
I already tried tracing on paper and stepping into code, but couldn't understand: 1. What role the sorting plays. 2. How the final area is being calculated without swapping any column as the question demands !
Any help is highly appreciated !
- What role the sorting plays.
- How the final area is being calculated without swapping any column as the question demands !
The sorting IS the swapping of columns. If we look at the 3rd row under step 2:
3 3 1 0 0 The sorted row corresponds to swapping the columns so that the column with the highest possible rectangle is placed first, after that comes the column that allows the second highest rectangle and so on. So, in the example there are 2 columns that can form a rectangle of height 3. That makes an area of 3*2=6. If we try to make the rectangle wider the height drops to 1, because there are no columns left that allow a higher rectangle on the 3rd row.
Edit: Avoiding unnecessary sorting
Using a standard O(n*log(n)) sorting algorithm gives us good performance.
It is possible to reduce the sorting needed by avoiding unnecessary sorting. The suggestions that follow won't reduce the O rating, but it will reduce the number of swaps substantially.
To reduce the number of swaps we need to abort the sorting of a row as soon as possible. To be able to do that I recommend using quicksort and always sort the left partition (higher numbers) first. Whenever the pivot times the partition size is smaller than the largest rectangle we have found so far, we know that the right partition (lower numbers) cannot hold the largest rectangle, so we can skip sorting the right partition.
Example:
Assume that the largest rectangle found so far has size 6 and the next row to sort looks like this:
1 3 0 3 0 We take the first element, 1 as pivot. The pivot times the partition size is 1 * 5 = 5, which is less than or equal to the largest size found. This means that we can skip the right partition, since it cannot yield a rectangle larger than 5.
3 3 (keep sorting this partition) - 1 0 0 (skip this partition)
Mergesort only allows us to skip parts of the final merge, so that's why I'd go with quicksort.
def rectangle(matrix): R = len(matrix) C = len(matrix[0]) mtrx = [] for i in range(R): row = [] for j in range(C): #creating a matrix of 0 row.append(0) mtrx.append(row) for i in range(C): #copy first row matrix mtrx[0][i] = matrix[0][i] #counting the consecutive ones for j in range(R): if matrix[j][i] == 0: mtrx[j][i] = 0 else: mtrx[j][i] = mtrx[j-1][i]+1 #sort the rows for i in range(R): mtrx[i] = sorted(mtrx[i],reverse=True) #Traverse the sorted matrix to find maximum area max_area = 0 for i in range(R): for j in range(C): current = (j+1) * mtrx[i][j] if current > max_area: max_area = current return max_area matrix = [[0, 1, 0, 1, 0], [0, 1, 0, 1, 1], [1, 1, 0, 1, 0]] 