Saddle_Point

#include <iostream>

using namespace std;

#define MAT_SIZE 5
int mat[MAT_SIZE][MAT_SIZE] = { 11, 3, 5, 6, 9, 12, 4, 7, 8, 10, 10, 5, 6, 9, 11, 8, 6, 4, 7, 2, 15, 10, 11, 20, 25 };

// #define MAT_SIZE 3
// int mat[MAT_SIZE][MAT_SIZE] = { 12, 34, 23, 34, 45, 34, 35, 45, 34 };

bool Solution1()
{
    bool found = false;

    for (int i = 0; i < MAT_SIZE; i++) {
        int max_j = 0;
        int min_i = 0;
        bool flag = true;

        for (int j = 1; j < MAT_SIZE; j++) {
            if (mat[i][j] > mat[i][max_j]) {
                max_j = j;
            }
        }

        for (int k = 0; k < MAT_SIZE; k++) {
            if (k == i) {
                continue;
            } else if (mat[k][max_j] < mat[i][max_j]) {
                flag = false;
                break;
            }
        }

        if (flag) {
            found = true;
            cout << i << '\t' << max_j << '\t' << mat[i][max_j] << endl;
        }
    }

    return found;
}

bool Solution2()
{
    bool found = false;

    int row_max[MAT_SIZE] = { 0 };
    int col_min[MAT_SIZE] = { 0 };

    for (int i = 0; i < MAT_SIZE; i++) {
        for (int j = 1; j < MAT_SIZE; j++) {
            if (mat[i][j] > mat[i][row_max[i]]) {
                row_max[i] = j;
            }
        }
    }

    for (int j = 0; j < MAT_SIZE; j++) {
        for (int i = 1; i < MAT_SIZE; i++) {
            if (mat[i][j] < mat[col_min[j]][j]) {
                col_min[j] = i;
            }
        }
    }

    for (int k = 0; k < MAT_SIZE; k++) {
        if (col_min[row_max[k]] == k) {
            found = true;
            cout << k << '\t' << row_max[k] << '\t' << mat[k][row_max[k]] << endl;
        }
    }

    return found;
}

int main()
{
    if (!Solution1()) {
        cout << "Not Found" << endl;
    }

    if (!Solution2()) {
        cout << "Not Found" << endl;
    }
}