Matrix Cells in Distance Order

Easy
305.

Matrix Cells in Distance Order

Matrix Cells in Distance Order is an easy coding problem on arrays, math and sorting, asked in Amazon, Adobe and Yahoo interviews.

You are given four integers describing a rows × cols matrix and a starting cell (rCenter, cCenter).

Return the coordinates of all the cells, sorted by their Manhattan distance from the centre. Ties are broken by row and then by column, both ascending.

The Manhattan distance between (r1, c1) and (r2, c2) is abs(r1 - r2) + abs(c1 - c2).

Example 1

Input
rows = 1, cols = 2, rCenter = 0, cCenter = 0
Output
[[0,0],[0,1]]

Example 2

Input
rows = 2, cols = 2, rCenter = 0, cCenter = 1
Output
[[0,1],[0,0],[1,1],[1,0]]

Example 3

Input
rows = 2, cols = 3, rCenter = 1, cCenter = 2
Output
[[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]

Constraints

  • 1 <= rows, cols <= 8
  • 0 <= rCenter < rows
  • 0 <= cCenter < cols
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} rows
 * @param {number} cols
 * @param {number} rCenter
 * @param {number} cCenter
 * @return {number[][]}
 */
var allCellsDistOrder = function(rows, cols, rCenter, cCenter) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Matrix Cells in Distance Order — Problem & Solution

Matrix Cells in Distance Order solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Matrix Cells in Distance Order is an easy coding problem on arrays, math and sorting, asked in Amazon, Adobe and Yahoo interviews.

  • Difficulty: Easy
  • Topics: Arrays, Math, Sorting, Matrix
  • Asked at: Amazon, Adobe, Yahoo
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given four integers describing a rows × cols matrix and a starting cell (rCenter, cCenter).

Return the coordinates of all the cells, sorted by their Manhattan distance from the centre. Ties are broken by row and then by column, both ascending.

The Manhattan distance between (r1, c1) and (r2, c2) is abs(r1 - r2) + abs(c1 - c2).

Example 1

Input: rows = 1, cols = 2, rCenter = 0, cCenter = 0
Output: [[0,0],[0,1]]

Example 2

Input: rows = 2, cols = 2, rCenter = 0, cCenter = 1
Output: [[0,1],[0,0],[1,1],[1,0]]

Example 3

Input: rows = 2, cols = 3, rCenter = 1, cCenter = 2
Output: [[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]

Constraints

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

Hints for Matrix Cells in Distance Order

  1. Hint 1

    Generate every cell, then sort by the distance key.

  2. Hint 2

    State the tie-break explicitly — distance alone leaves many valid orders, and this problem fixes one.

  3. Hint 3

    A bucket sort by distance also works, since the distance is bounded by rows + cols.

How to solve Matrix Cells in Distance Order

Generate every cell and sort by (distance, row, column).

Approach

  1. List all [r, c].
  2. Sort with key (|r - rCenter| + |c - cCenter|, r, c).

Why it works

The composite key encodes the required order including the stated tie-break, so a stable comparison sort produces exactly the expected output.

Complexity

  • Time — O(rc · log(rc))
  • Space — O(rc)

Pitfalls

  • Distance is bounded by rows + cols, so bucket sort by distance is linear if needed.

Reference solution

Python

def allCellsDistOrder(rows: int, cols: int, rCenter: int, cCenter: int):
    cells = [[r, c] for r in range(rows) for c in range(cols)]
    cells.sort(key=lambda cell: (abs(cell[0] - rCenter) + abs(cell[1] - cCenter), cell[0], cell[1]))
    return cells

Java

public static int[][] allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
    int[][] cells = new int[rows * cols][2];
    int pos = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            cells[pos][0] = r;
            cells[pos][1] = c;
            pos++;
        }
    }
    Arrays.sort(cells, new Comparator<int[]>() {
        public int compare(int[] a, int[] 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);
            if (da != db) return da - db;
            if (a[0] != b[0]) return a[0] - b[0];
            return a[1] - b[1];
        }
    });
    return cells;
}

C++

vector<vector<int>> allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
    vector<vector<int>> cells;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) cells.push_back({r, c});
    }
    sort(cells.begin(), cells.end(), [rCenter, cCenter](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);
        if (da != db) return da < db;
        if (a[0] != b[0]) return a[0] < b[0];
        return a[1] < b[1];
    });
    return cells;
}

JavaScript

var allCellsDistOrder = function(rows, cols, rCenter, cCenter) {
    const cells = [];
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) cells.push([r, c]);
    }
    cells.sort(function(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);
        if (da !== db) return da - db;
        if (a[0] !== b[0]) return a[0] - b[0];
        return a[1] - b[1];
    });
    return cells;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms