Matrix Cells in Distance Order - Practice Coding Problems

Matrix Cells in Distance Order - Problem

Array Math Geometry Sorting Matrix Easy

You are given four integers rows, 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 (r1, c1) and (r2, c2) is |r1 - r2| + |c1 - c2| (Manhattan distance).

Input & Output

Example 1 — Small Matrix

$ Input: rows = 1, cols = 2, rCenter = 0, cCenter = 0

› Output: [[0,0],[0,1]]

💡 Note: Only 2 cells: (0,0) at distance 0 and (0,1) at distance 1. Manhattan distance from (0,0): |0-0|+|0-0|=0 for (0,0), |0-0|+|1-0|=1 for (0,1).

Example 2 — Center Position

$ Input: rows = 2, cols = 2, rCenter = 0, cCenter = 1

› Output: [[0,1],[0,0],[1,1],[1,0]]

💡 Note: Center (0,1): distance 0. Adjacent cells (0,0) and (1,1) at distance 1. Diagonal (1,0) at distance 2. Order: d=0 → d=1 → d=1 → d=2.

Example 3 — Corner Center

$ Input: rows = 2, cols = 3, rCenter = 1, cCenter = 2

› Output: [[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]

💡 Note: Center at corner (1,2). Distances: (1,2)=0, (0,2)=1, (1,1)=1, (0,1)=2, (1,0)=2, (0,0)=3. Cells are naturally grouped by distance levels.

Constraints

1 ≤ rows, cols ≤ 100
0 ≤ rCenter < rows
0 ≤ cCenter < cols

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

2×3 matrix with center at (0,1)

Calculate Distances

Manhattan distance from each cell to center

Sort by Distance

Return coordinates in increasing distance order

Key Takeaway

🎯 Key Insight: Manhattan distance creates natural concentric layers around the center point

Asked in

G Google 45 a Amazon 32 f Facebook 28

The key insight is using Manhattan distance |r1-r2|+|c1-c2| to sort matrix cells. BFS approach is optimal as it naturally discovers cells in distance order without sorting. Time: O(mn), Space: O(mn).

Common Approaches

Approach	Time	Space	Notes
✓ Bucket Sort by Distance	O(mn)	O(mn + d)	Group cells by distance, then process buckets in order
Breadth-First Search (BFS)	O(mn)	O(mn)	Use BFS to naturally traverse cells in distance order
Brute Force with Sorting	O(mn log(mn))	O(mn)	Generate all coordinates, calculate distances, then sort

Bucket Sort by Distance — Algorithm Steps

Calculate maximum possible distance
Create buckets for each distance value
Group cells into appropriate buckets
Output buckets in order

Visualization

Tap to expand

Step-by-Step Walkthrough

Create Distance Buckets

Make buckets for distances 0 to maxDistance

Group Cells by Distance

Place each cell in its distance bucket

Concatenate Buckets

Combine buckets in distance order

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int** solution(int rows, int cols, int rCenter, int cCenter, int* returnSize, int** returnColumnSizes) {
    int maxDistance = max(rCenter, rows - 1 - rCenter) + max(cCenter, cols - 1 - cCenter);
    
    // Create buckets
    int*** buckets = malloc((maxDistance + 1) * sizeof(int**));
    int* bucketSizes = calloc(maxDistance + 1, sizeof(int));
    int* bucketCapacities = malloc((maxDistance + 1) * sizeof(int));
    
    for (int i = 0; i <= maxDistance; i++) {
        bucketCapacities[i] = rows * cols;
        buckets[i] = malloc(bucketCapacities[i] * sizeof(int*));
    }
    
    // Fill buckets
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            int distance = abs(r - rCenter) + abs(c - cCenter);
            buckets[distance][bucketSizes[distance]] = malloc(2 * sizeof(int));
            buckets[distance][bucketSizes[distance]][0] = r;
            buckets[distance][bucketSizes[distance]][1] = c;
            bucketSizes[distance]++;
        }
    }
    
    // Collect results
    *returnSize = rows * cols;
    *returnColumnSizes = malloc(*returnSize * sizeof(int));
    int** result = malloc(*returnSize * sizeof(int*));
    
    int idx = 0;
    for (int d = 0; d <= maxDistance; d++) {
        for (int i = 0; i < bucketSizes[d]; i++) {
            result[idx] = malloc(2 * sizeof(int));
            result[idx][0] = buckets[d][i][0];
            result[idx][1] = buckets[d][i][1];
            (*returnColumnSizes)[idx] = 2;
            idx++;
        }
    }
    
    return result;
}

int main() {
    int rows, cols, rCenter, cCenter;
    scanf("%d %d %d %d", &rows, &cols, &rCenter, &cCenter);
    
    int returnSize;
    int* returnColumnSizes;
    int** result = solution(rows, cols, rCenter, cCenter, &returnSize, &returnColumnSizes);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("[%d,%d]", result[i][0], result[i][1]);
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(mn)

Visit each cell once O(mn), bucket operations are O(1)

✓ Linear Growth

Space Complexity

O(mn + d)

Result array O(mn) plus buckets for max distance d

⚡ Linearithmic Space

34.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bucket Sort by Distance — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler