Sort a 2D vector diagonally (asked in microsoft)
Tue Jan 25 2022 06:55:45 GMT+0000 (Coordinated Universal Time)
Saved by
@vaibhav_55
//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
}
}
}
}
content_copyCOPY
Comments