The only square is found when s=2. Your program will look at s=3 and not
find a square, so it will never find the square.
Try it and you will see what I mean..
Don
On Monday, March 31, 2014 2:42:13 PM UTC-4, atul007 wrote:
>
> @Don: what is the point of considering s=2 when we have already fou
@Don: what is the point of considering s=2 when we have already found
s=3.As question says find "the maximum subsquare". Which is of size 3 and
this the expected outcome.
On Mon, Mar 31, 2014 at 11:28 PM, Don wrote:
> 00
> 00
> 010100
> 011100
> 01
> 00
>
> In this case, when i
00
00
010100
011100
01
00
In this case, when i and j are 1, your algorithm will set s = 3. The if
statement will fail, and it will never notice that it could have formed a
square with s=2.
Don
On Sunday, March 30, 2014 9:49:21 AM UTC-4, atul007 wrote:
>
> @don : According to q
@don : According to question we want to find "the maximum subsquare".
can you give me test case for which this wont work?
On Fri, Mar 28, 2014 at 9:41 PM, Don wrote:
> No, that is not the same.
> It won't find a square smaller than s.
> Don
>
>
> On Thursday, March 27, 2014 2:56:29 AM UTC-4,
No, that is not the same.
It won't find a square smaller than s.
Don
On Thursday, March 27, 2014 2:56:29 AM UTC-4, atul007 wrote:
>
> @Don : your algo time complexity is O(n^2)
>
> It can be reduced to this :-
>
> // Now look for largest square with top left corner at (i,j)
> for(i = 0; i < n
@Don : your algo time complexity is O(n^2)
It can be reduced to this :-
// Now look for largest square with top left corner at (i,j)
for(i = 0; i < n; ++i)
for(j = 0; j < n; ++j)
{
s = Min(countRight[i][j], countDown[i][j]);
if (countRight[i][j] && countDown[
The worst case I know of is when the matrix is solid black except for
the lower right quadrant. In this case, it does break down into O(n^3)
runtime. It took about 8 times as long to run n=4000 as it took for
n=2000.
Don
On Jan 24, 10:29 am, Don wrote:
> I'm not sure I understand your case. Howev
I'm not sure I understand your case. However, I stated that there are
cases where it is worse than O(N^2). The runtime is highly dependent
on the contents of the matrix. In many cases it takes fewer than N^2
iterations. Occasionally it takes more. On average it seems to be
roughly O(N^2), but again
@Don: the solution is very nice.. But, how can u prove that it is O(n^2)..
for me it seems to be O(n^3) ..
Ex: nxn matrix .. all 1s from (n/2,0) to (n/2,n/2).
all 1s from (n/2,0) to (n,0).
On Thu, Jan 17, 2013 at 9:28 PM, Don wrote:
> The downside is that it uses a bunch of extra space.
> The u
The downside is that it uses a bunch of extra space.
The upside is that it is pretty fast. It only does the time-consuming
task of scanning the matrix for contiguous pixels once, it only
searches for squares larger than what it has already found, and it
doesn't look in places where such squares cou
awesome solution Don . Thanks.
On Thursday, January 17, 2013 12:38:35 AM UTC+5:30, marti wrote:
>
> Imagine there is a square matrix with n x n cells. Each cell is either
> filled with a black pixel or a white pixel. Design an algorithm to find the
> maximum subsquare such that all four borders
int countRight[n][n];
int countDown[n][n];
int i,j,s;
int bestI, bestJ, max=0;
int lastRight, lastDown = n;
// Start by setting countRight[i][j] to the number of consecutive
// black pixels starting at (i,j) and moving right
// and countDown[i][j] to the number of consecutive black pixels
// star
Looking at this, I realized that I need to reset lastRight=lastDown=n
inside the first loop, before the for(j=n-1 loop
On Jan 16, 2:59 pm, Don wrote:
> int countRight[n][n];
> int countDown[n][n];
>
> int i,j,s;
> int bestI, bestJ, max=0;
> int lastRight = n;
> int lastDown = n;
>
> // Start by s
int countRight[n][n];
int countDown[n][n];
int i,j,s;
int bestI, bestJ, max=0;
int lastRight = n;
int lastDown = n;
// Start by setting countRight[i][j] to the number of consecutive
black pixels starting at (i,j) and moving right
// and countDown[i][j] to the number of consecutive black pixels
st
14 matches
Mail list logo
