https://leetcode.com/problems/sort-the-matrix-diagonally/

1. Use STL sort():

  1. //20 ms    9.5 MB
  3. class Solution {
  4. public:
  5.     vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
  6.         //top-right [0][n-1]
  7.         //buttom-left [m-1][0]
  9.         //m = 3, n = 4
  10.         //[0][n-1]
  11.         //[0][n-2] [1][n-1]  i = 1
  12.         //[0][n-3] [1][n-2] [2][n-1]  i = 2
  13.         //[0][0] [1][n-3] [2][n-2]  i = 3
  15.         //[1][0] [2][1] i = 4
  16.         //[2][0] i = 5
  18.         //i = total of difference
  19.         //v = vertical difference
  20.         //h = horizontal difference
  21.         //v + h == i
  23.         int m = mat.size();
  24.         int n = mat[0].size();
  26.         for(int i=0; i<m+n-1; i++){
  27.             Find_And_Fill_Diagonals(i, mat, m, n);
  28.         }
  30.         return mat;
  31.     }
  33. private:
  34.     void Find_And_Fill_Diagonals(int diff, vector<vector<int>>& mat, int m, int n){
  35.         vector<int> diagonal;
  37.         int v_init;
  38.         int h_init;
  40.         if(diff<=n-1){
  41.             v_init = 0;
  42.             h_init = n-1-diff;
  43.         } else{
  44.             v_init = diff-n+1;
  45.             h_init = 0;
  46.         }
  48.         int v_curr = v_init;
  49.         int h_curr = h_init;
  50.         while(v_curr<m && h_curr<n){
  51.             diagonal.push_back(mat[v_curr][h_curr]);
  52.             v_curr++;
  53.             h_curr++;
  54.         }
  56.         sort(diagonal.begin(), diagonal.end());
  58.         v_curr = v_init;
  59.         h_curr = h_init;
  60.         for(int i=0; i<diagonal.size(); i++){
  61.             mat[v_curr][h_curr] = diagonal[i];
  62.             v_curr++;
  63.             h_curr++;
  64.         }
  65.     }
  67. };

Time Complexity: O(m*n)
Space Complexity: O(sqrt(m^2 + n^2))