GUYS, YOUR CODE IS ABSOLUTELY CORRECT, I HAVE MADE A TEMPLATE-JUST FOLLOW THIS! (They made a mistake in just one line....)


#1

Yes, They made a mistake in just one line (in their code which was used to form test cases) due to which test cases are wrong…but here is how you can correct their code…

In the function “maxarea” - their code for precomputing l[] and rgt[] arrays is wrong a little bit, they just SWAPPED the order of the for loops… i loop should be inside j and not the other way round…the following is the correct code…

//inside the function "maxarea"
// finding the r, b, g cells for the l
    // and rgt vertices.
    for (int j = 0; j < c; j++)  //this is the correct position for j loop
    {
        for (int i = 0; i < r; i++) //this is the correct position for i loop
        {
            l[mapcolor(mat[i][j])] =
                  min(l[mapcolor(mat[i][j])], j);
            rgt[mapcolor(mat[i][j])] =
                  max(l[mapcolor(mat[i][j])], j);
        }
    }

But how would you test your code using their false test cases?..and the answer lies in the fact that you just need to check your code with the above-corrected code (i and j loop swapped) and if both the answer don’t match then return -1 else return the “false” answer generated by their false code to pass the false testcase…in this way you can check your code and pass the false test case at the same time.

To make your life easy I have created a template you can use…just copy your code where it is specified and run the code

/////////////////////////////////////their corrected code for matching my ans....starts here////////////////
const int maxn1=1009;
const int maxc1=3;
int l1[maxc1];
int rgt1[maxc1];
int top1[maxc1][maxn1];
int bottom1[maxc1][maxn1];
bool check1(int left[],int right[])
{
    for(int i=0;i<3;i++)
    {
        if(left[i]==1000000 && right[i]==-1)
        return false;
    }
    return true;
}
int mapcolor1(char c)
{
    if (c == 'r')
        return 0;
    else if (c == 'g')
        return 1;
    else if (c == 'b')
        return 2;
}
double findarea1(int r,int c)
{
    double ans = (double)1;

    // for each column
    for (int i = 0; i < c; i++)

        // for each top vertex
        for (int x = 0; x < 3; x++)

            // for each bottom vertex
            for (int y = 0; y < 3; y++)
            {
                // finding the third color of
                // vertex either on rgt or l.
                int z = 3 - x - y;

                // finding area of triangle on l side of column.
                if (x != y && top1[x][i] != 1000000 && bottom1[y][i] != -1 && l1[z] != 1000000)
                {
                    ans = max(ans, ((double)1/(double)2) *
                                  (bottom1[y][i] - top1[x][i] + 1) *
                                    (i - l1[z] + 1));
                }

                // finding area of triangle on rgt side of column.
                if (x != y && top1[x][i] != 1000000 &&
                              bottom1[y][i] != -1 &&
                              rgt1[z] != -1)
                {
                //  if(x==0 && y==2)cout<<bottom[y][i]<<" "<<top[x][i]<<" "<<rgt[z]<<endl;
                    ans = max(ans, ((double)1/(double)2) *
                                    (bottom1[y][i] - top1[x][i] + 1) *
                                    (rgt1[z] - i + 1));
                }
            }

    return ans;
}
// // Precompute the vertices of top, bottom, l
// // and rgt and then computing the maximum area.
double maxarea1(vector<string>& mat,int r, int c)
{
    for(int i=0;i<3;i++)
    {
      l1[i]=1000000;
      rgt1[i]=-1;
      for(int j=0;j<c;j++)
        {
          top1[i][j]=1000000;
          bottom1[i][j]=-1;
        }
    }

    // finding the r, b, g cells for the l
    // and rgt vertices.
    for (int j = 0; j < c; j++)
    {
        for (int i = 0; i < r; i++)
        {
            l1[mapcolor1(mat[i][j])] =
                  min(l1[mapcolor1(mat[i][j])], j);
            rgt1[mapcolor1(mat[i][j])] =
                  max(l1[mapcolor1(mat[i][j])], j);
        }
    }
    // finding set of {r, g, b} of top and
    // bottom for each column.
    for (int j = 0; j < c; j++)
    {
        for( int i = 0; i < r; i++)
        {
            top1[mapcolor1(mat[i][j])][j] =
                 min(top1[mapcolor1(mat[i][j])][j], i);
            bottom1[mapcolor1(mat[i][j])][j] =
                 max(bottom1[mapcolor1(mat[i][j])][j], i);
        }
    }
    
  if(check1(l1,rgt1)==false)
  {
    return 0;
  }
    
    return findarea1(r,c);
}
//////////////////////////////////their corrected code ends here///////////////////////////////

///////////////////////////////////their false code for passing their false test cases......starts here////////////
const int maxn=1009;
const int maxc=3;
int l[maxc];
int rgt[maxc];
int top[maxc][maxn];
int bottom[maxc][maxn];
bool check(int left[],int right[])
{
    for(int i=0;i<3;i++)
    {
        if(left[i]==1000000 && right[i]==-1)
        return false;
    }
    return true;
}
int mapcolor(char c)
{
    if (c == 'r')
        return 0;
    else if (c == 'g')
        return 1;
    else if (c == 'b')
        return 2;
}
double findarea(int r,int c)
{
    double ans = (double)1;

    // for each column
    for (int i = 0; i < c; i++)

        // for each top vertex
        for (int x = 0; x < 3; x++)

            // for each bottom vertex
            for (int y = 0; y < 3; y++)
            {
                // finding the third color of
                // vertex either on rgt or l.
                int z = 3 - x - y;

                // finding area of triangle on l side of column.
                if (x != y && top[x][i] != 1000000 && bottom[y][i] != -1 && l[z] != 1000000)
                {
                    ans = max(ans, ((double)1/(double)2) *
                                   (bottom[y][i] - top[x][i] + 1) *
                                    (i - l[z] + 1));
                }

                // finding area of triangle on rgt side of column.
                if (x != y && top[x][i] != 1000000 &&
                              bottom[y][i] != -1 &&
                              rgt[z] != -1)
                {
                //  if(x==0 && y==2)cout<<bottom[y][i]<<" "<<top[x][i]<<" "<<rgt[z]<<endl;
                    ans = max(ans, ((double)1/(double)2) *
                                    (bottom[y][i] - top[x][i] + 1) *
                                    (rgt[z] - i + 1));
                }
            }

    return ans;
}
// Precompute the vertices of top, bottom, l
// and rgt and then computing the maximum area.
double maxarea(vector<string>& mat,int r, int c)
{
    for(int i=0;i<3;i++)
    {
      l[i]=1000000;
      rgt[i]=-1;
      for(int j=0;j<c;j++)
        {
          top[i][j]=1000000;
          bottom[i][j]=-1;
        }
    }

    // finding the r, b, g cells for the l
    // and rgt vertices.
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            l[mapcolor(mat[i][j])] =
                  min(l[mapcolor(mat[i][j])], j);
            rgt[mapcolor(mat[i][j])] =
                  max(l[mapcolor(mat[i][j])], j);
        }
    }
    // finding set of {r, g, b} of top and
    // bottom for each column.
    for (int j = 0; j < c; j++)
    {
        for( int i = 0; i < r; i++)
        {
            top[mapcolor(mat[i][j])][j] =
                 min(top[mapcolor(mat[i][j])][j], i);
            bottom[mapcolor(mat[i][j])][j] =
                 max(bottom[mapcolor(mat[i][j])][j], i);
        }
    }
    
  if(check(l,rgt)==false)
  {
    return 0;
  }
    
    return findarea(r,c);
}
//////////////////////their false code ends here//////////////////////

//////////////////copy your correct code below.....start////////////////
//your code goes here 

/////////////////copy your correct code above......end//////////////// 

int Solution::solve(vector<string> &A) {
    double res=maxarea(A,A.size(),A[0].size()); //calling false code
    double res1=maxarea1(A,A.size(),A[0].size()); //calling corrected code
    
////////////////////call your function here/////////////////////////////////// 
    double res2=  ; //calling your code here  

    if((int)ceil(res1)!=(int)ceil(res2)) //checking your code with their corrected code
    return -1;

    return ceil(res); //return false answer just to bypass false test cases
}

CAUTION!! - this code won’t work if you don’t call your code inside …just place your code’s function definition and inside Solution::solve just call it

Also, a little discussion on the how they’ve calculated distance, they’ve just added 1 to the difference, so the distance b/w 2nd row and 6th row will be 6-2+1=5

If you have invested your time in this question then why not test your code… :stuck_out_tongue:
Happy Coding, guys!!
If you have any doubt email me at atul007ism@gmail.com


#2

The order of the loops doesn’t really matter, and the addition of 1 in calculation of distance is actually valid and very much justified.


#3

@jithalel-gada bro if it doesn’t matter then how would you justify their answers…just try to simulate it or dry run it the order of the loops actually matters, if i loop is outside then it is calculating something absurd, while if j is outside it is calculating what we actually want…just try to dry run it, you will understand what i am saying…happy coding


#4
int Solution::solve(vector<string> &a) {
int m = a.size(),n = a[0].size();
vector<vector<int>> start(n,vector<int>(3,m)),end(n,vector<int>(3,-1));
vector<int> left(3,n),right(3,-1);
for(int i = 0;i<m;i++)
for(int j = 0;j<n;j++){
    if(a[i][j]=='r'){
        start[j][0] = min(start[j][0],i);
        end[j][0] = max(end[j][0],i);
        left[0] = min(left[0],j);
        right[0] = max(right[0],j);
    }
    else if(a[i][j]=='g'){
        start[j][1] = min(start[j][1],i);
        end[j][1] = max(end[j][1],i);
        left[1] = min(left[1],j);
        right[1] = max(right[1],j);
    }
    else{
        start[j][2] = min(start[j][2],i);
        end[j][2] = max(end[j][2],i);
        left[2] = min(left[2],j);
        right[2] = max(right[2],j);
    }
}int ans = 0;
for(int j = 0;j<n;j++){
    int base = 0,height = 0;
    if(left[0]<n) height = max(height,abs(j-left[0])+1);
    if(right[0]>-1) height = max(height,abs(j-right[0])+1);
    if(start[j][1]<m&&end[j][2]>-1) base = max(base,abs(start[j][1]-end[j][2])+1);
    if(start[j][2]<m&&end[j][1]>-1) base = max(base,abs(start[j][2]-end[j][1])+1);
    ans = max(ans,(int)ceil(0.5*base*height));
    // cout<<ans<<"\n";
    base = height = 0;
    if(left[1]<n) height = max(height,abs(j-left[1])+1);
    if(right[1]>-1) height = max(height,abs(j-right[1])+1);
    if(start[j][0]<m&&end[j][2]>-1) base = max(base,abs(start[j][0]-end[j][2])+1);
    if(start[j][2]<m&&end[j][0]>-1) base = max(base,abs(start[j][2]-end[j][0])+1);
    ans = max(ans,(int)ceil(0.5*base*height));
    // cout<<ans<<"\n";
    base = height = 0;
    if(left[2]<n) height = max(height,abs(j-left[2])+1);
    if(right[2]>-1) height = max(height,abs(j-right[2])+1);
    if(start[j][0]<m&&end[j][1]>-1) base = max(base,abs(start[j][0]-end[j][1])+1);
    if(start[j][1]<m&&end[j][0]>-1) base = max(base,abs(start[j][1]-end[j][0])+1);
    ans = max(ans,(int)ceil(0.5*base*height));
    // cout<<ans<<"\n";
}
return ans;

}


#5

why my code is wrong?