CareerCup

This is the problem of largest area histogram. Compute sum of rows by iterative deepening (row-wise), and for every 1-D array generated get largest area histogram for it.
Finally return the maximum.
----------------------------------------------------------
Program to find largest area of histogram.

int largestArea(int arr[], int len)  
{  
    int area[len]; //initialize it to 0  
    int n, i, t;  
    stack<int> St;  //include stack for using this #include<stack>  
    bool done;  
      
    for (i=0; i<len; i++)  
    {  
        while (!St.empty())  
        {  
            if(arr[i] <= arr[St.top()])  
            {  
               St.pop();  
            }  
            else  
               break;  
        }  
       if(St.empty())  
            t = -1;  
      else  
           t = St.top();  
      //Calculating Li  
      area[i] = i - t - 1;  
      St.push(i);  
    }  
      
    //clearing stack for finding Ri  
    while (!St.empty())  
       St.pop();  
      
    for (i=len-1; i>=0; i--)  
    {  
       while (!St.empty())  
       {  
          if(arr[i] <= arr[St.top()])  
          {  
              St.pop();  
          }  
         else  
             break;  
       }  
       if(St.empty())  
          t = len;  
       else  
          t = St.top();  
       //calculating Ri, after this step area[i] = Li + Ri  
      area[i] += t - i -1;  
      St.push(i);  
    }  
      
    int max = 0;  
    //Calculating Area[i] and find max Area  
    for (i=0; i<len; i++)  
    {  
       area[i] = arr[i] * (area[i] + 1);  
       if (area[i] > max)  
          max = area[i];  
     }  

    return max;  
}

----------------------------------------------------

Program to get 1-D array by summing each row every time.
---------------------------------------------------------

#define ROW 10  
#define COL 10  
      
int find_max_matrix(int A[ROW][COL])  
{  
     int i, j;  
     int max, cur_max;  
     cur_max = 0;  
      
     //Calculate Auxilary matrix  
     for (i=1; i<ROW; i++)  
         for(j=0; j<COL; j++)  
         {  
             if(A[i][j] == 1)  
                 A[i][j] = A[i-1][j] + 1;  
         }  
      
     //Calculate maximum area in S for each row  
     for (i=0; i<ROW; i++)  
     {       
         max = largestArea(A[i], COL);  
         if (max > cur_max)  
             cur_max = max;  
     }  
      
     //Regenerate Oriignal matrix  
     for (i=ROW-1; i>0; i--)  
         for(j=0; j<COL; j++)  
         {  
             if(A[i][j])  
                 A[i][j] = A[i][j] - A[i-1][j];  
         }  
      
     return cur_max;  
}

can yo explain more about this Question and which company ask this Question

Can 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 }

Consider this matrix
0 1 1 0 0
0 0 0 1 1
0 1 0 1 1
0 1 1 1 0
0 1 1 1 0
1 0 1 1 0

At every row i will do a[i] && a[i+i]
Which will give me if i am able to form any new rectangles
Simultaneously i will maintain a max heap of rectangles
Rectangle = corner1, corner2, area.
Optional step
I will remove a rectangle if it is evident there can be no more 1's added to it and it is not the Max area rectangle.
I will then do a a[i] && a[i-1] and see if the any previous rectangles can be increased in size.
If so i will do so.
In the end i will output the max from heap.

here's how it will go

Just showing this for explanation i am not changing the array or taking extra array.
0 1 1 0 0
0 0 0 2 2
0 0 0 2 2
0 6 6 6 0
0 6 6/8 6/8 0
0 0 8 8 0


List of Rectangles
1 corner1,corner2 size=2
3 corner1,corner2 size=4
6 corner1,corner2 size=6
8 corner1,corner2 size=4
Max Size = 6

Complexity -- I am only scanning the array once. But each time i may have to look at all the previous rectangles which may be.

O( rows * (number of rectangles) )

use a new matrix sum[row][column][2] which represents the sum of left 1s and top 1s
say
1,1,0,1,0
0,1,1,1,0
1,1,1,0,1
1,0,1,1,0
you'll have a new matrix sum[0][0]={1,1} sum[0][1]={2,1}, etc
so you can check from bottom right to top left of this matrix to get the each rectangle's area, and each element will be visited once, which has time complexity O(row*column).

can someone plz give me O(N log^3( N)) solution for this problem

change all 0 to a negetive infinite and then maximum sum algo for 2D