Mixing
Find the largest rectangle of 1’s with swapping of columns allowed
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 !
algorithm matrix
asked Sep 10 '15 at 7:56
vinitvinit
132110
add a comment |
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 !
algorithm matrix
asked Sep 10 '15 at 7:56
vinitvinit
132110
1
The question is not related to programming - it's about an algorithm which apply regardless of whether you write a program to implement it or you do it by hand using a piece of paper. I'll suggest you try to ask it at a math site instead. If you have problems implementing the algorithm or understanding the suggested implementation then this is the site to ask.
– 4386427
Sep 10 '15 at 8:47
add a comment |
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 !
algorithm matrix
asked Sep 10 '15 at 7:56
vinitvinit
132110
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 !
algorithm matrix
algorithm matrix
asked Sep 10 '15 at 7:56
vinitvinit
132110
asked Sep 10 '15 at 7:56
vinitvinit
132110
edited Sep 10 '15 at 9:15
vinit
asked Sep 10 '15 at 7:56
vinitvinit
132110
asked Sep 10 '15 at 7:56
vinitvinit
132110
asked Sep 10 '15 at 7:56
vinitvinit
132110
132110
1
The question is not related to programming - it's about an algorithm which apply regardless of whether you write a program to implement it or you do it by hand using a piece of paper. I'll suggest you try to ask it at a math site instead. If you have problems implementing the algorithm or understanding the suggested implementation then this is the site to ask.
– 4386427
Sep 10 '15 at 8:47
add a comment |
1
The question is not related to programming - it's about an algorithm which apply regardless of whether you write a program to implement it or you do it by hand using a piece of paper. I'll suggest you try to ask it at a math site instead. If you have problems implementing the algorithm or understanding the suggested implementation then this is the site to ask.
– 4386427
Sep 10 '15 at 8:47
1
1
The question is not related to programming - it's about an algorithm which apply regardless of whether you write a program to implement it or you do it by hand using a piece of paper. I'll suggest you try to ask it at a math site instead. If you have problems implementing the algorithm or understanding the suggested implementation then this is the site to ask.
– 4386427
Sep 10 '15 at 8:47
The question is not related to programming - it's about an algorithm which apply regardless of whether you write a program to implement it or you do it by hand using a piece of paper. I'll suggest you try to ask it at a math site instead. If you have problems implementing the algorithm or understanding the suggested implementation then this is the site to ask.
– 4386427
Sep 10 '15 at 8:47
add a comment |
2 Answers
2
active
oldest
votes
- 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.
answered Sep 10 '15 at 10:54
Klas LindbäckKlas Lindbäck
30.5k44371
Thanks, that was helpful !
– vinit
Sep 10 '15 at 14:21
how to restrict swaps to minimum. @Klas Lindbäck
– Xax
Jul 26 '16 at 7:40
1
@Xax Se question edit.
– Klas Lindbäck
Jul 26 '16 at 8:01
if you can pls elaborate a bit more @KlasLindbäck thanks
– Xax
Jul 26 '16 at 8:44
1
@Xax I've added an example.
– Klas Lindbäck
Jul 26 '16 at 9:31
add a comment |
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]]
answered Jan 2 at 6:51
Eye SunEye Sun
12
While this code may answer the question, it is better to explain how to solve the problem and provide the code as an example or reference. Code-only answers can be confusing and lack context.
– Dima Kozhevin
Jan 2 at 7:45
This is for people who understand how to read codes. I have left comment, and I implemented the algorithm from the link given in Python
– Eye Sun
Jan 3 at 0:04
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f32496214%2ffind-the-largest-rectangle-of-1-s-with-swapping-of-columns-allowed%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
- 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.
answered Sep 10 '15 at 10:54
Klas LindbäckKlas Lindbäck
30.5k44371
Thanks, that was helpful !
– vinit
Sep 10 '15 at 14:21
how to restrict swaps to minimum. @Klas Lindbäck
– Xax
Jul 26 '16 at 7:40
1
@Xax Se question edit.
– Klas Lindbäck
Jul 26 '16 at 8:01
if you can pls elaborate a bit more @KlasLindbäck thanks
– Xax
Jul 26 '16 at 8:44
1
@Xax I've added an example.
– Klas Lindbäck
Jul 26 '16 at 9:31
add a comment |
- 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.
answered Sep 10 '15 at 10:54
Klas LindbäckKlas Lindbäck
30.5k44371
Thanks, that was helpful !
– vinit
Sep 10 '15 at 14:21
how to restrict swaps to minimum. @Klas Lindbäck
– Xax
Jul 26 '16 at 7:40
1
@Xax Se question edit.
– Klas Lindbäck
Jul 26 '16 at 8:01
if you can pls elaborate a bit more @KlasLindbäck thanks
– Xax
Jul 26 '16 at 8:44
1
@Xax I've added an example.
– Klas Lindbäck
Jul 26 '16 at 9:31
add a comment |
- 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.
answered Sep 10 '15 at 10:54
Klas LindbäckKlas Lindbäck
30.5k44371
- 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.
answered Sep 10 '15 at 10:54
Klas LindbäckKlas Lindbäck
30.5k44371
edited Jul 26 '16 at 9:30
answered Sep 10 '15 at 10:54
Klas LindbäckKlas Lindbäck
30.5k44371
answered Sep 10 '15 at 10:54
Klas LindbäckKlas Lindbäck
30.5k44371
answered Sep 10 '15 at 10:54
Klas LindbäckKlas Lindbäck
30.5k44371
30.5k44371
Thanks, that was helpful !
– vinit
Sep 10 '15 at 14:21
how to restrict swaps to minimum. @Klas Lindbäck
– Xax
Jul 26 '16 at 7:40
1
@Xax Se question edit.
– Klas Lindbäck
Jul 26 '16 at 8:01
if you can pls elaborate a bit more @KlasLindbäck thanks
– Xax
Jul 26 '16 at 8:44
1
@Xax I've added an example.
– Klas Lindbäck
Jul 26 '16 at 9:31
add a comment |
Thanks, that was helpful !
– vinit
Sep 10 '15 at 14:21
how to restrict swaps to minimum. @Klas Lindbäck
– Xax
Jul 26 '16 at 7:40
1
@Xax Se question edit.
– Klas Lindbäck
Jul 26 '16 at 8:01
if you can pls elaborate a bit more @KlasLindbäck thanks
– Xax
Jul 26 '16 at 8:44
1
@Xax I've added an example.
– Klas Lindbäck
Jul 26 '16 at 9:31
Thanks, that was helpful !
– vinit
Sep 10 '15 at 14:21
Thanks, that was helpful !
– vinit
Sep 10 '15 at 14:21
how to restrict swaps to minimum. @Klas Lindbäck
– Xax
Jul 26 '16 at 7:40
how to restrict swaps to minimum. @Klas Lindbäck
– Xax
Jul 26 '16 at 7:40
1
1
@Xax Se question edit.
– Klas Lindbäck
Jul 26 '16 at 8:01
@Xax Se question edit.
– Klas Lindbäck
Jul 26 '16 at 8:01
if you can pls elaborate a bit more @KlasLindbäck thanks
– Xax
Jul 26 '16 at 8:44
if you can pls elaborate a bit more @KlasLindbäck thanks
– Xax
Jul 26 '16 at 8:44
1
1
@Xax I've added an example.
– Klas Lindbäck
Jul 26 '16 at 9:31
@Xax I've added an example.
– Klas Lindbäck
Jul 26 '16 at 9:31
add a comment |
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]]
answered Jan 2 at 6:51
Eye SunEye Sun
12
While this code may answer the question, it is better to explain how to solve the problem and provide the code as an example or reference. Code-only answers can be confusing and lack context.
– Dima Kozhevin
Jan 2 at 7:45
This is for people who understand how to read codes. I have left comment, and I implemented the algorithm from the link given in Python
– Eye Sun
Jan 3 at 0:04
add a comment |
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]]
answered Jan 2 at 6:51
Eye SunEye Sun
12
While this code may answer the question, it is better to explain how to solve the problem and provide the code as an example or reference. Code-only answers can be confusing and lack context.
– Dima Kozhevin
Jan 2 at 7:45
This is for people who understand how to read codes. I have left comment, and I implemented the algorithm from the link given in Python
– Eye Sun
Jan 3 at 0:04
add a comment |
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]]
answered Jan 2 at 6:51
Eye SunEye Sun
12
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]]
answered Jan 2 at 6:51
Eye SunEye Sun
12
answered Jan 2 at 6:51
Eye SunEye Sun
12
answered Jan 2 at 6:51
Eye SunEye Sun
12
answered Jan 2 at 6:51
Eye SunEye Sun
12
12
While this code may answer the question, it is better to explain how to solve the problem and provide the code as an example or reference. Code-only answers can be confusing and lack context.
– Dima Kozhevin
Jan 2 at 7:45
This is for people who understand how to read codes. I have left comment, and I implemented the algorithm from the link given in Python
– Eye Sun
Jan 3 at 0:04
add a comment |
While this code may answer the question, it is better to explain how to solve the problem and provide the code as an example or reference. Code-only answers can be confusing and lack context.
– Dima Kozhevin
Jan 2 at 7:45
This is for people who understand how to read codes. I have left comment, and I implemented the algorithm from the link given in Python
– Eye Sun
Jan 3 at 0:04
While this code may answer the question, it is better to explain how to solve the problem and provide the code as an example or reference. Code-only answers can be confusing and lack context.
– Dima Kozhevin
Jan 2 at 7:45
While this code may answer the question, it is better to explain how to solve the problem and provide the code as an example or reference. Code-only answers can be confusing and lack context.
– Dima Kozhevin
Jan 2 at 7:45
This is for people who understand how to read codes. I have left comment, and I implemented the algorithm from the link given in Python
– Eye Sun
Jan 3 at 0:04
This is for people who understand how to read codes. I have left comment, and I implemented the algorithm from the link given in Python
– Eye Sun
Jan 3 at 0:04
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f32496214%2ffind-the-largest-rectangle-of-1-s-with-swapping-of-columns-allowed%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
The question is not related to programming - it's about an algorithm which apply regardless of whether you write a program to implement it or you do it by hand using a piece of paper. I'll suggest you try to ask it at a math site instead. If you have problems implementing the algorithm or understanding the suggested implementation then this is the site to ask.
– 4386427
Sep 10 '15 at 8:47