Problem statement

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

Solution

Just create defaultdict of values: for each cell we put pair: distance -> cell.

Complexity

Time and space complexity is O(mn).

Code

class Solution:
    def allCellsDistOrder(self, rows, cols, rCenter, cCenter):
        d = defaultdict(list)
        for r in range(rows):
            for c in range(cols):
                d[abs(r - rCenter) + abs(c - cCenter)].append((r, c))
                
        i, ans = 0, []
        while i in d:
            ans.extend(d[i])
            i += 1
        return ans