Tendulkar
BAN USERCan be done in O(n2)
Here is the alog:
a[n][n]
O/p: updating 4 points of a rectangle (A, B, C, D)
1. Start from a[0][0] and find out first 1 in the array
A = step1 output
2. Loop starts from step 1 element (i, j)
{ a. another loop to get 1 in the same colomn (starting from end towards j) }, if no 1 exists in the current col, then increment A colomn number and start from begenning.
{ b. B = stepa output
{ c. From B start another loop to get corresponding right edge by getting extreme in the same row, if no 1 found decrement B row number and start from step a
{ d. C = output of stepc }
{ e. start a loop at C , to find top point in the same col }, if not found decrement C and start from step c }
{ d. if D and A are on the same col, break all loops (A, B, C, D is the output)
{ If ( D and A are not in the same col, then get tow pointer from A and D and find out common element where both have 1, we can search until we reach the B, if not found rectangle doesnt exists with the given data, other wise return A, B , C and D }
Nice Idea Aks, but ur code fails for some inputs .... I did some modifications to handle all cases
postOrderIterative(node *root)
{
node *prev=null, *elem;
push(root);
while(StackIsnotempty())
{
elem = getTop();
if(elem>left == NULL && elem>right == NULL)
{
print(elem);
pop();
prev=elem;
continue;
}
if(elem>left == prev)
{
if(elem>right == NULL)
{
print(elem);
pop();
prev = elem;
continue;
}
push(elem>right);
}
else if(elem>left != NULL)
{
push(elem>left);
}
if(elem>right == prev)
{
print(elem);
pop();
prev=elem;
}
}
}

Tendulkar
September 07, 2012
Find sum of all the numbers ... which would be the size of o/p array
 Tendulkar February 20, 2013Now start from array+size and come backwards by filling all the elements ....
i/p array = a1b2
size = 1+2 = 3
array+(size1) = b
array+(size2) = b
array+(size3) = a