Diagonal Sorting Algorithm in a Matrix

Given a two-dimensional integer matrix, sort each of the diagonals descending from left to right in ascending order.

Constraints
n, m ≤ 25 where n and m are the rows and columns of matrix
Example 1
Input

matrix = [
    [9, 8, 7],
    [6, 5, 4],
    [3, 2, 1]
]

Output

[
    [1, 4, 7],
    [2, 5, 8],
    [3, 6, 9]
]

Sort and Fill the Diagonals

We can iterate each diagonals (there are R + C – 1 diagonals), store them in a vector, sort the vector, and then re-visit each diagonals to update the value in the diagonal to the sorted version. This will take O((R + C – 1) * D * Log(D)) time where R, C, D are rows, columns, and size of the largest diagonals respectively.

The space complexity is O(D) as we need to copy over the diagonals and sort it.

vector<vector<int>> solve(vector<vector<int>>& matrix) {
    int rows = matrix.size();
    if (0 == rows) return matrix;
    int cols = matrix[0].size();
    for (int r = 0; r < rows; ++ r) {
        vector<int> d;
        int y = r, x = 0;
        while (y < rows && x < cols) {
            d.push_back(matrix[y][x]);
            y ++;
            x ++;
        }
        sort(begin(d), end(d));
        y = r, x = 0;
        int i = 0;
        while (y < rows && x < cols) {
            matrix[y][x] = d[i ++];
            y ++;
            x ++;
        }        
    }
    for (int c = 0; c < cols; ++ c) {
        vector<int> d;
        int y = 0, x = c;
        while (y < rows && x < cols) {
            d.push_back(matrix[y][x]);
            y ++;
            x ++;
        }
        sort(begin(d), end(d));
        y = 0, x = c;
        int i = 0;
        while (y < rows && x < cols) {
            matrix[y][x] = d[i ++];
            y ++;
            x ++;
        }        
    }    
    return matrix;
}

Using a Priority Queue to do Diagonal Sorting

The elements in the same diagonals have the same value of rowIndex-colIndex. Thus we can use a map to store the key as the diagonals and values would be pushed as we iterate over the matrix:

vector<vector<int>> solve(vector<vector<int>>& matrix) {
    map<int, priority_queue<int, vector<int>, greater<int>>> m;
    int r = matrix.size();
    int c = matrix[0].size();

    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            m[i - j].push(matrix[i][j]);
        }
    }

    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            matrix[i][j] = m[i - j].top();
            m[i - j].pop();
        }
    }

    return matrix;
}

The time complexity is O(RCLogD). Space complexity is O(RC).

–EOF (The Ultimate Computing & Technology Blog) —