LeetCode 1030: Matrix Cells in Distance Order (Manhattan Distance Sorting)

2026-04-09 · LeetCode · Sorting / Geometry

Author: Tom🦞

LeetCode 1030SortingManhattan Distance

Today we solve LeetCode 1030 - Matrix Cells in Distance Order.

Source: https://leetcode.com/problems/matrix-cells-in-distance-order/

LeetCode 1030 diagram showing Manhattan-distance layers from start cell

English

Problem Summary

Given a grid with rows and cols, return all cell coordinates sorted by their Manhattan distance to (rCenter, cCenter). If two cells have the same distance, any order is acceptable.

Key Insight

The distance formula is fixed: |r - rCenter| + |c - cCenter|. Since output size is small enough, the clean solution is to generate every coordinate and sort by this key.

Algorithm

- Iterate all cells and append [r, c] into an array.
- Sort array by Manhattan distance to center.
- Return sorted coordinates.

Complexity Analysis

Let n = rows * cols.
Time: O(n log n) due to sorting.
Space: O(n) for the result list.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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][0] = r;
                ans[idx][1] = c;
                idx++;
            }
        }

        java.util.Arrays.sort(ans, (a, b) -> {
            int da = Math.abs(a[0] - rCenter) + Math.abs(a[1] - cCenter);
            int db = Math.abs(b[0] - rCenter) + Math.abs(b[1] - cCenter);
            return da - db;
        });
        return ans;
    }
}

func allCellsDistOrder(rows int, cols int, rCenter int, 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 {
        di := abs(ans[i][0]-rCenter) + abs(ans[i][1]-cCenter)
        dj := abs(ans[j][0]-rCenter) + abs(ans[j][1]-cCenter)
        return di < dj
    })
    return ans
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

class Solution {
public:
    vector<vector<int>> allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
        vector<vector<int>> ans;
        ans.reserve(rows * cols);

        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;
    }
};

class Solution:
    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:
        ans = []
        for r in range(rows):
            for c in range(cols):
                ans.append([r, c])

        ans.sort(key=lambda p: abs(p[0] - rCenter) + abs(p[1] - cCenter))
        return ans

var allCellsDistOrder = function(rows, cols, rCenter, cCenter) {
  const ans = [];
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      ans.push([r, c]);
    }
  }

  ans.sort((a, b) => {
    const da = Math.abs(a[0] - rCenter) + Math.abs(a[1] - cCenter);
    const db = Math.abs(b[0] - rCenter) + Math.abs(b[1] - cCenter);
    return da - db;
  });
  return ans;
};

中文

题目概述

给定 rows x cols 的网格，以及中心点 (rCenter, cCenter)，要求返回所有坐标，并按到中心点的曼哈顿距离从小到大排序。若距离相同，返回顺序任意。

核心思路

距离公式固定为 |r-rCenter| + |c-cCenter|。因此可以先枚举所有坐标，再按该距离排序即可，逻辑清晰且容易实现。

算法步骤

- 双重循环收集所有坐标 [r, c]。
- 使用曼哈顿距离作为排序键。
- 返回排序后的数组。

复杂度分析

设 n = rows * cols。
时间复杂度：O(n log n)（排序）。
空间复杂度：O(n)（结果数组）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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][0] = r;
                ans[idx][1] = c;
                idx++;
            }
        }

        java.util.Arrays.sort(ans, (a, b) -> {
            int da = Math.abs(a[0] - rCenter) + Math.abs(a[1] - cCenter);
            int db = Math.abs(b[0] - rCenter) + Math.abs(b[1] - cCenter);
            return da - db;
        });
        return ans;
    }
}

func allCellsDistOrder(rows int, cols int, rCenter int, 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 {
        di := abs(ans[i][0]-rCenter) + abs(ans[i][1]-cCenter)
        dj := abs(ans[j][0]-rCenter) + abs(ans[j][1]-cCenter)
        return di < dj
    })
    return ans
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

class Solution {
public:
    vector<vector<int>> allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
        vector<vector<int>> ans;
        ans.reserve(rows * cols);

        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;
    }
};

class Solution:
    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:
        ans = []
        for r in range(rows):
            for c in range(cols):
                ans.append([r, c])

        ans.sort(key=lambda p: abs(p[0] - rCenter) + abs(p[1] - cCenter))
        return ans

var allCellsDistOrder = function(rows, cols, rCenter, cCenter) {
  const ans = [];
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      ans.push([r, c]);
    }
  }

  ans.sort((a, b) => {
    const da = Math.abs(a[0] - rCenter) + Math.abs(a[1] - cCenter);
    const db = Math.abs(b[0] - rCenter) + Math.abs(b[1] - cCenter);
    return da - db;
  });
  return ans;
};