1030. Matrix Cells in Distance Order

You are given four integers row, cols, rCenter, and cCenter. There is a rows x cols matrix and you are on the cell with the coordinates (rCenter, cCenter).

Return the coordinates of all cells in the matrix, sorted by their distance from (rCenter, cCenter) from the smallest distance to the largest distance. You may return the answer in any order that satisfies this condition.

The distance between two cells $(r_1,c_1)$ and $(r_2,c_2)$ is $|r_1-r_2|+|c_1-c_2|$.
 

Example 1:

Input: rows = 1, cols = 2, rCenter = 0, cCenter = 0
Output: [[0,0],[0,1]]
Explanation: The distances from (0, 0) to other cells are: [0,1]

Example 2:

Input: rows = 2, cols = 2, rCenter = 0, cCenter = 1
Output: [[0,1],[0,0],[1,1],[1,0]]
Explanation: The distances from (0, 1) to other cells are: [0,1,1,2]
The answer [[0,1],[1,1],[0,0],[1,0]] would also be accepted as correct.

Example 3:

Input: rows = 2, cols = 3, rCenter = 1, cCenter = 2
Output: [[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]
Explanation: The distances from (1, 2) to other cells are: [0,1,1,2,2,3]
There are other answers that would also be accepted as correct, such as [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]].

Constraints:

• 1 <= rows, cols <= 100
• 0 <= rCenter < rows
• 0 <= cCenter < cols

From: LeetCode
Link: 1030. Matrix Cells in Distance Order

Solution:

Ideas:

• Store every cell with its Manhattan distance to (rCenter, cCenter).
• Sort all cells by distance.
• Build the required int** result array.

Code:

typedef struct {
    int r;
    int c;
    int dist;
} Cell;

static int cmp(const void *a, const void *b) {
    Cell *x = (Cell *)a;
    Cell *y = (Cell *)b;
    return x->dist - y->dist;
}

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** allCellsDistOrder(int rows, int cols, int rCenter, int cCenter, int* returnSize, int** returnColumnSizes) {
    int total = rows * cols;
    *returnSize = total;

    Cell *cells = (Cell *)malloc(sizeof(Cell) * total);
    int idx = 0;

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            cells[idx].r = i;
            cells[idx].c = j;
            cells[idx].dist = abs(i - rCenter) + abs(j - cCenter);
            idx++;
        }
    }

    qsort(cells, total, sizeof(Cell), cmp);

    int **result = (int **)malloc(sizeof(int *) * total);
    *returnColumnSizes = (int *)malloc(sizeof(int) * total);

    for (int i = 0; i < total; i++) {
        result[i] = (int *)malloc(sizeof(int) * 2);
        result[i][0] = cells[i].r;
        result[i][1] = cells[i].c;
        (*returnColumnSizes)[i] = 2;
    }

    free(cells);
    return result;
}