Skip to main content

Largest Square, rectangular

you are given a M x N matrix with 0's and 1's find the matrix-

1. find the largest square matrix with all elements 1's
2. Find the largest rectangular matrix with all elements 1's


Its simple DP problem guys ..just think of extending the solution to sub-problem.
Will post answer soon..till then give it a try.

Okie so recursive expression is
SQ(i,j) = MIN(SQ(i-1,j),SQ(i-1,j-1),SQ(i,j-1))*ARR(i,j)+ARR(i,j);

Idea is that SQ(i,j) will be a 1+ min of its precedents square size.


I am multiplying and adding to avoid if else condition
if ( ARR[i][j] == 1 )
SQ(i,j) = MIN(SQ(i-1,j),SQ(i-1,j-1),SQ(i,j-1))+1;
else
SQ(i,j) = 0;

is same as this SQ(i,j) = MIN(SQ(i-1,j),SQ(i-1,j-1),SQ(i,j-1))*ARR(i,j)+ARR(i,j);

Will post code soon.
Labels:

Comments

  1. AshuDecember 24, 2009 at 4:07 AM

    Source code:

    #include

    using namespace std;
    int const size = 6;

    int min( int a, int b, int c )
    {
    cout <<(a<b?(a<c?a:c):(b<c?b:c))<<endl;
    return (a<b?(a<c?a:c):(b<c?b:c));
    }
    int main()
    {
    int arr[size][size] = {
    { 0, 0 , 0 , 0, 1, 0 },
    { 0, 1 , 1 , 1, 0, 1 },
    { 0, 1 , 1 , 0, 0, 0 },
    { 1, 0 , 1 , 1, 1, 1 },
    { 0, 0 , 1 , 1, 1, 0 },
    { 0, 1 , 1 , 1, 1, 1 }};

    int result[size+1][size+1];
    int i, j;
    for ( i = 0; i < size;i++)
    {
    result[i][0] = 0;
    result[0][i] = 0;
    }
    for ( i = 1; i < size+1;i++)
    {
    for ( j = 1; j < size+1;j++)
    {
    if ( arr[i-1][j-1] == 0 )
    result[i][j] = 0;
    else
    result[i][j] = min(result[i-1][j],result[i-1][j-1],result[i][j-1])+1;
    }
    }
    for ( i = 0; i < size+1;i++)
    {
    for ( j = 0; j < size+1;j++)
    {
    cout<<result[i][j]<<" ";
    }
    cout<<endl;
    }


    return 0;
    }

    ReplyDelete

Post a Comment

Popular posts from this blog

Car Parking Problem

There is n parking slots and n-1 car already parked. Lets say car parked with initial arrangement and we want to make the car to be parked to some other arrangement. Lets say n = 5, inital = free, 3, 4, 1, 2 desired = 1, free, 2, 4 ,3 Give an algorithm with minimum steps needed to get desired arrangement. Told by one of my friend and after a lot of search i really got a nice solution. I will post solution in comment part
3 comments
Read more

DEShaw Interview Questions

ther are N numbers frm 1 to N and starting from index 1 we will keep deleting every alternate going in cyclic order with array. Only one element will be left at the end. Tell us the index of element in array we started. e.g. there are 5 nums 1 2 3 4 5 then after 1st iteration 1 3 5 will be remained. .. then 1 will be next to be elliminated and then 5 3 will remain alone... give sum efficient algorithm to calculate which numer will remain at the end Answer: 2*(n-2^p)+1 where p=floor(log2 n)
Post a Comment
Read more

Permutations Sum(xi)

You have given "k" dice. How many way you can get a sum "S" and yes you have to throw all the dice. Write program for this. Its same permutations program...but we have to try with all the six S(1,2,3,4,5,6) possibilities for a dice. Exit condition will be If all the dice run out. SumP(dice,sum) = SumP(dice-1,sum-i)+i (from S).
1 comment
Read more