Optimal solution of Maximum Area of Triangle with comments

interview-questions
programming
Tags: #<Tag:0x00007f2425392c40> #<Tag:0x00007f2425392b00>

#1
int Solution::solve(vector<string> &a) 

{
int n = a.size();
int m = a[0].size();

int dp[m][3];
int top[m][3];

//Area of Triangle is = 1/2 * base * height

for(int i=0;i<m;i++)
    top[i][0] = top[i][1] = top[i][2] = 0;

for(int i=0;i<m;i++) //finding max base for ( case1 : base = bg, case2: base = rb, case3: base = rg)
{
    int h1=0,gup,gdown,rup,rdown,bup,bdown;
    gup = gdown, bup = bdown = rup = rdown = -1;

    while(h1<n)
    {
        if(a[h1][i]=='r')
        {
            rup=h1;
            break;
        }
        h1++;
    }
    h1=0;
    while(h1<n)
    {
        if(a[h1][i]=='g')
        {
            gup=h1;
            break;
        }
        h1++;
    }
    h1=0;
    while(h1<n)
    {
        if(a[h1][i]=='b')
        {
            bup=h1;
            break;
        }
        h1++;
    }

    h1 = n-1;
    while(h1>=0)
    {
        if(a[h1][i]=='r')
        {
            rdown = h1;
            break;
        }
        h1--;
    }
    h1 = n-1;
    while(h1>=0)
    {
        if(a[h1][i]=='g')
        {
            gdown = h1;
            break;
        }
        h1--;
    }
    h1 = n-1;
    while(h1>=0)
    {
        if(a[h1][i]=='b')
        {
            bdown = h1;
            break;
        }
        h1--;
    }


    dp[i][0] = max(abs(gup-bdown) , abs(gdown-bup))+1;
    if(gup==-1 || bup==-1) dp[i][0] = 0;
    dp[i][1] = max(abs(rup-bdown) , abs(rdown-bup))+1;
    if(rup==-1 || bup==-1) dp[i][1] = 0;
    dp[i][2] = max(abs(rup-gdown) , abs(rdown-gup))+1;
    if(rup==-1 || gup==-1) dp[i][2] = 0;

    if(rup==-1) top[i][0] = -1;
    if(gup==-1) top[i][1] = -1;
    if(bup==-1) top[i][2] = -1;
}

int rfront,rback,gback,gfront,bback,bfront;
rfront = rback = gback = gfront = bback = bfront = -1;

//Findind max height if top is not set to be -1
for(int i=m-1;i>=0;i--)  if(top[i][0]==0){rback=i;break;}
for(int i=0;i<m;i++)     if(top[i][0]==0){rfront=i;break;}
for(int i=m-1;i>=0;i--)  if(top[i][1]==0){gback=i;break;}
for(int i=0;i<m;i++)     if(top[i][1]==0){gfront=i;break;}
for(int i=m-1;i>=0;i--)  if(top[i][2]==0){bback=i;break;}
for(int i=0;i<m;i++)     if(top[i][2]==0){bfront=i;break;}

//Finding partial area, i.e. base*height
for(int i=0;i<m;i++)
 {
    dp[i][0]=(max(abs(i-rfront),abs(i-rback))+1)*dp[i][0];
    dp[i][1]=(max(abs(i-gfront),abs(i-gback))+1)*dp[i][1];
    dp[i][2]=(max(abs(i-bfront),abs(i-bback))+1)*dp[i][2];
     
    if(rfront==-1)dp[i][0]=0;
    if(gfront==-1)dp[i][1]=0;
    if(bfront==-1)dp[i][2]=0;
 }

int ans=0;
//taking max partial area 
for(int i=0;i<m;i++)  ans=max(ans,max(dp[i][0],max(dp[i][1],dp[i][2])));
 

//return ceil of (partial-area /2)
return ans/2+ans%2;

}