//Link to question :- https://practice.geeksforgeeks.org/problems/diagonal-morning-assembly0028/1/
/*
Steps:-
    1.store the upper triangle in a array of vectors at index to difference of their index
    2.do similary for lower triangle
    3.now sort each array in array of vectors
            lower one sort in ascending
            upper one sort in decending
    4.now place the values in correct place in original matrix
    
    
    Time Complexity: O(N*M*log(min(N,M)))
	Space Complexity: O(N*M)
    
*/

void sort_martix_diagonally(vector<vector<int>> &matrix, int n, int m)
{

    vector<int> upper[m + 1]; // array of vectors to store the upper triangle
    vector<int> lower[n + 1]; // array of vectors to store the lower triangle

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (i == j)
                continue; // if it is diagonal continue
            else if (i < j)
            {
                int ind = abs(i - j);
                upper[ind].push_back(matrix[i][j]); // storing the upper triangle at proper index
            }
            else if (i > j)
            {
                int ind = abs(i - j);
                lower[ind].push_back(matrix[i][j]); // storing the lower triangle at proper index
            }
        }
    }

    // sorting each vector
    for (auto &&v : lower)
    {
        sort(v.begin(), v.end()); // sorting in asceding order the lower triangle
    }

    for (auto &&v : upper)
    {
        sort(v.rbegin(), v.rend()); ////sorting in decending order the upper triangle
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (i == j)
                continue;
            else if (i < j)
            {
                int ind = abs(i - j);
                matrix[i][j] = upper[ind][i]; // putting the sorted values in proper
            }
            else if (i > j)
            {
                int ind = abs(i - j);
                matrix[i][j] = lower[ind][j]; // putting the sorted values in proper
            }
        }
    }
}