Very Simple solution with O(n^2) time & O(n) space complexity


#1

Comment body goes here.`const pair<int, int> inf = {-1, -1};

int findOtherCol(int curr, vector<pair<int, int>>& col){
int height = 0;
for(int i=0;i<col.size();i++){
if(i != curr && col[i] != inf)
height = max(height, abs(i-curr)+1);
}

return height;

}

int Solution::solve(vector &A) {
int n=A.size();
if(n<2)return 0;
int m=A[0].length();
if(m<2)return 0;

vector<pair<int, int>> r(m, inf), g(m, inf), b(m, inf);

for(int j=0;j<n;j++){
    string s = A[j];
    for(int i=0;i<m;i++){
        if(s[i]=='r'){
            if(r[i].first == -1)r[i].first = j;
            r[i].second = j;
        }
        else if(s[i]=='g'){
            if(g[i].first == -1)g[i].first = j;
            g[i].second = j;
        }
        else{
            if(b[i].first == -1)b[i].first = j;
            b[i].second = j;
        }
    }
}

int ans = 0;
for(int i=0;i<m;i++){
    int r_b = -1, r_g = -1, b_g = -1;
    if(r[i] != inf && b[i] != inf)
        r_b = max(abs(r[i].first-b[i].second), abs(r[i].second-b[i].first));
    if(r[i] != inf && g[i] != inf)
        r_g = max(abs(r[i].first-g[i].second), abs(r[i].second-g[i].first));
    if(b[i] != inf && g[i] != inf)
        b_g = max(abs(b[i].first-g[i].second), abs(b[i].second-g[i].first));
    
    int curr_side = max(r_b, max(r_g, b_g));
    if(curr_side < 0) continue;
    
    int height = 0;
    if(curr_side == r_b){
        // find g int other cols.
        height = findOtherCol(i, g);
        
    }
    else if(curr_side == r_g){
        // find b int other cols.
        height = findOtherCol(i, b);
        
    }
    else{
        // find r in the other cols.
        height = findOtherCol(i, r);
    }
    
    // for the curr ith column, i got curr_side as the max length of the
    // vertical side. 
    
    // cout<<i<<" ("<<curr_side+1<<","<<height<<"), ";

    int curr_area = curr_side + 1;
    curr_area *= height;
    curr_area = (curr_area+1)/2;
    
    ans = max(ans, curr_area);
}

return ans;

}
`

n : # rows.
m : # columns.

The Idea is: for every column store the first & last occurence of each color in r[m], g[m], b[m]. O(n) space.

Then for each column, if there exist 2 colors , find the maximum length of vertical side (RG, RB, BG) (can be done in O(1) time from the stored values in vectors r, g, b). and corresponding to the the maximum length side, find the third color in the rest of column (in O(M) time using the stored values in vectors r, g, b) and store it in height.

now maxArea for currColumn = (length of vertical side * height ) / 2. (take ceil of it).

Thanks.


#2

This is the best solution!
Hands down
I wonder what is the purpose of giving such problem in interviewbit ?