Problem

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 theirdistance 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 (r1, c1) and (r2, c2) is |r1 - r2| + |c1 - c2|.

Examples

Example 1

1
2
3

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

1
2
3
4

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

1
2
3
4

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

Solution

Method 1 – Sorting by Manhattan Distance

Intuition

The Manhattan distance between two cells is the sum of the absolute differences of their row and column indices. We can generate all cell coordinates and sort them by their distance to the center cell.

Approach

  1. Generate all cell coordinates (r, c) for the matrix.
  2. For each cell, compute its Manhattan distance to (rCenter, cCenter).
  3. Sort the list of coordinates by this distance.
  4. Return the sorted list.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    vector<vector<int>> allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
        vector<vector<int>> ans;
        for (int r = 0; r < rows; ++r)
            for (int c = 0; c < cols; ++c)
                ans.push_back({r, c});
        sort(ans.begin(), ans.end(), [&](const vector<int>& a, const vector<int>& b) {
            int da = abs(a[0] - rCenter) + abs(a[1] - cCenter);
            int db = abs(b[0] - rCenter) + abs(b[1] - cCenter);
            return da < db;
        });
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func allCellsDistOrder(rows, cols, rCenter, cCenter int) [][]int {
    ans := make([][]int, 0, rows*cols)
    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            ans = append(ans, []int{r, c})
        }
    }
    sort.Slice(ans, func(i, j int) bool {
        da := abs(ans[i][0]-rCenter) + abs(ans[i][1]-cCenter)
        db := abs(ans[j][0]-rCenter) + abs(ans[j][1]-cCenter)
        return da < db
    })
    return ans
}
func abs(x int) int { if x < 0 { return -x }; return x }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int[][] allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
        int[][] ans = new int[rows*cols][2];
        int idx = 0;
        for (int r = 0; r < rows; r++)
            for (int c = 0; c < cols; c++)
                ans[idx++] = new int[]{r, c};
        Arrays.sort(ans, (a, b) -> (Math.abs(a[0]-rCenter) + Math.abs(a[1]-cCenter)) - (Math.abs(b[0]-rCenter) + Math.abs(b[1]-cCenter)));
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    fun allCellsDistOrder(rows: Int, cols: Int, rCenter: Int, cCenter: Int): Array<IntArray> {
        val ans = mutableListOf<IntArray>()
        for (r in 0 until rows)
            for (c in 0 until cols)
                ans.add(intArrayOf(r, c))
        ans.sortBy { Math.abs(it[0]-rCenter) + Math.abs(it[1]-cCenter) }
        return ans.toTypedArray()
    }
}
1
2
3
4
5

class Solution:
    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> list[list[int]]:
        ans = [[r, c] for r in range(rows) for c in range(cols)]
        ans.sort(key=lambda x: abs(x[0]-rCenter) + abs(x[1]-cCenter))
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
    pub fn all_cells_dist_order(rows: i32, cols: i32, r_center: i32, c_center: i32) -> Vec<Vec<i32>> {
        let mut ans = vec![];
        for r in 0..rows {
            for c in 0..cols {
                ans.push(vec![r, c]);
            }
        }
        ans.sort_by_key(|x| (x[0]-r_center).abs() + (x[1]-c_center).abs());
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    allCellsDistOrder(rows: number, cols: number, rCenter: number, cCenter: number): number[][] {
        const ans: number[][] = [];
        for (let r = 0; r < rows; r++)
            for (let c = 0; c < cols; c++)
                ans.push([r, c]);
        ans.sort((a, b) => Math.abs(a[0]-rCenter) + Math.abs(a[1]-cCenter) - (Math.abs(b[0]-rCenter) + Math.abs(b[1]-cCenter)));
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(mn log(mn)), where m and n are the matrix dimensions, for sorting all cells.
  • 🧺 Space complexity: O(mn), for storing all cell coordinates.