Find Largest Area Triangle from 2D Matrix

Problem:
Given a table of size n * m, with each cell having a color value from the set {r, g, b}, find the area of the largest triangle that has one side parallel with the y – axis (vertical) and has no two vertices that have the same color value.

Input :
First line contains the size of the matrix i.e. n * m where n is the number of rows and m is the number of columns.
n lines follow each having a string of size m.

Output :
A single value for the area of the triangle.

Solution :
Since we have one side parallel to the y – axis we will treat this side as the base of the triangle. The area of a triangle can be written as (1 / 2) * base * height. So the problem reduces to maximising the value of the base and the height. We also want that all the vertices should have different values. Lets first consider the task of maximising the base.
pre-computation :
For each column we can find the first and the last occurrence of the value of {r, g, b}. So we will get 2 sets of 3 values. It can be easily seen that if the base is in this column then it must have one vertex from the first set and the second vertex from the second set such that the values are not the same. This can be done in O(n * m).
Given the base of the column now we have to maximise the height. The height of the triangle will be maximum of the distance of this column from the farthest point on the left or the right having value different from the other 2 vertices of the triangle. This farthest point can be calculated in O(n * m) time.

Now the solution can be found by once iterating through all the columns, and for each column calculating the maximum area of triangle that has base in this column, using the information calculated above.

Code:

#include <bits/stdc++.h>

using namespace std;

#define MAXN 1000
#define MAXM 1000

//contains the first occurrence of the values in the column
int Top[3][MAXM];

//contains the last occurrence of the values in the column
int Bottom[3][MAXM];

//contains the first occurrence of the values in the row
int Left[3];

//contains the last occurrence of the values in the row
int Right[3];

vector <string> v;

//mapping for easy access
int mapping(char ch)
{
    if(ch == 'r') return 0;
    else if(ch == 'g') return 1;
    else if(ch == 'b') return 2;
}

void precompute(int n, int m)
{
    int i, j;

    Left[0] = MAXM, Left[1] = MAXM, Left[2] = MAXM;
    memset(Right, -1, sizeof Right);
    for(i = 0;i < MAXM; ++i) Top[0][i] = MAXN, Top[1][i] = MAXN, Top[2][i] = MAXN;
    memset(Bottom, -1, sizeof Bottom);

    //to find out global left and right color values
    for(i = 0;i < n; ++i){
        for(j = 0;j < m; ++j){
            Left[mapping(v[i][j])] = min(Left[mapping(v[i][j])], j);
            Right[mapping(v[i][j])] = max(Right[mapping(v[i][j])], j);
        }
    }

    //to find out top and bottom values for each column
    for(j = 0;j < m; ++j){
        for(i = 0;i < n; ++i){
            Top[mapping(v[i][j])][j] = min(Top[mapping(v[i][j])][j], i);
            Bottom[mapping(v[i][j])][j] = max(Bottom[mapping(v[i][j])][j], i);
        }
    }

}

double maximum_area(int n, int m)
{
    int i, s1, s2, s3;
    double ans = (double)1;
    //setting the column
    for(i = 0;i < m; ++i){
        //setting the two vertices in this column
        for(s1 = 0;s1 < 3; ++s1){
            for(s2 = 0;s2 < 3; ++s2){
                //finding the third vertex
                s3 = 3 - s1 - s2;
                if(s1 != s2 && Top[s1][i] != MAXN && Bottom[s2][i] != -1 && Left[s3] != MAXM){
                        ans = max(ans, ((double)1 / (double)2) * (Bottom[s2][i] - Top[s1][i]) * (i - Left[s3]));
                }
                if(s1 != s2 && Top[s1][i] != MAXN && Bottom[s2][i] != -1 && Right[s3] != -1){
                        ans = max(ans, ((double)1 / (double)2) * (Bottom[s2][i] - Top[s1][i]) * (Right[s3] - i));
                }
            }
        }
    }
    return ans;
}

int main()
{
    freopen("input.txt", "r", stdin);
    cout << "Enter the size of the matrix : \n";
    int n, m, i;
    cin >> n >> m;
    cout << "Enter the matrix : \n";
    for(i = 0;i < n; ++i){
        string temp;
        cin >> temp;
        v.push_back(temp);
    }
    precompute(n, m);
    cout << "The maximum possible area is : " << maximum_area(n, m);
    return 0;
}

Time Complexity :
O(n * m)