Problem 1030

Abstract / Summary

Given a matrix and a coordinate, list all cells sorted by their distance from that coordinate.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 1030.py

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

        return [ [ r, c ] for d, r, c in sorted(all) ]
10 lines | 387 bytes | submitted December 19, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 74% (100k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Geometry
  • Math
  • Matrix
  • Sorting
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The allCellsDistOrder method produces a list of every cell coordinate in a rectangular grid, ordered by their Manhattan distance from a specified centre cell. The grid dimensions are given by rows and cols, while rCenter and cCenter locate the centre. The result is a list of [row, col] pairs, with the nearest cells appearing first and the farthest last.

Key Steps

Generating all cell coordinates with distances

The method first creates an empty container named all. It then iterates over every possible row index r from 0 to rows-1 and, nested inside, over every column index c from 0 to cols-1. For each cell it computes the absolute horizontal offset dr as abs(cCenter - c) and the absolute vertical offset dc as abs(rCenter - r). The Manhattan distance is the sum dr + dc. A tuple containing the distance followed by the row and column indices is appended to all.

all = []
for r in range(rows):
    for c in range(cols):
        dr = abs(cCenter - c)
        dc = abs(rCenter - r)
        all.append((dr + dc, r, c))

Sorting by distance

After all tuples have been collected, the built-in sorted function is invoked on the list all. Because each tuple begins with the distance value, the default lexicographic ordering automatically sorts first by distance, then by row, and finally by column. This single call replaces any manual comparison logic and leverages the highly optimized Timsort algorithm in CPython.

sorted_all = sorted(all)

Producing the final list format

The sorted tuples are transformed into the required output shape using a list comprehension. For each tuple (d, r, c) the distance component d is discarded, and a two-element list [r, c] is emitted. The comprehension iterates over the sorted sequence, yielding the final ordered collection of cell coordinates.

return [[r, c] for d, r, c in sorted_all]

Edge Cases Handled

When either rows or cols is zero, the outer or inner loop executes no iterations, leaving all empty. The subsequent sort and list comprehension operate on an empty list, correctly returning an empty result without error.

If the centre coordinates rCenter or cCenter lie outside the bounds of the grid, the distance calculation still produces valid non-negative integers because it relies solely on absolute differences. The ordering remains consistent, and every cell in the grid is still included.

The algorithm also gracefully handles the smallest possible grid of size 1 × 1. The loops run once, the distance is zero, and the output is [[0, 0]].

Performance Optimizations

The implementation benefits from several implicit optimizations. First, the use of plain integer arithmetic (abs and addition) ensures that distance computation is fast and avoids any floating-point overhead.

Second, the choice of a flat list of tuples for intermediate storage allows the subsequent sorted call to work directly on contiguous memory, which is ideal for CPython’s Timsort. Because the distance is placed as the first element of each tuple, the sort does not need a custom key function, eliminating the extra function-call overhead that a key=lambda x: x[0] would incur.

Third, the final list comprehension constructs the output in a single pass, avoiding the need for an additional loop or temporary structures. This tight pipeline-from generation through sorting to final shaping-minimizes the number of passes over the data and keeps memory allocation to the essential containers only.

Overall, the code leverages Python’s built-in constructs to achieve a concise and efficient solution for ordering grid cells by Manhattan distance.

written by openai gpt

ELI5 - Simplified Explanation

Imagine a big grid of squares like a giant checkerboard laid out on the floor. Each square has its own special address made of two numbers, one for how far it is from the top and one for how far it is from the side.

The goal is to sort all of these square addresses by how close they are to a specific center spot. The code sets up an empty container to hold a list of all the squares. It then walks through every single square on the board one by one. For each square, it calculates the distance from the center by looking at how many steps it would take to travel left, right, up, or down.

Once it knows the distance for a square, it puts the distance value right next to the address of that square. After checking every spot on the entire board, the computer puts all these labels in a pile and sorts them by the distance number, starting with the ones that are closest to the center and moving to the ones that are furthest away. Finally, it cleans up the list so that only the address of the square is kept for each entry in the final sorted order.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 7 | μ = 6.93 | σ = 0.86

Complexity Analysis

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Java Python TS
WalkCCC C++ Java Python
leetcode.ca C++ Java Python Go
LeetcodeHelp C++ Java Python
MemoryLimitExceeded C++ Python
Progiez C++ Java Python
github BigEggStudy C#
black-shadows C++
charles-wangkai Java
DimitrisJim C
everthis JS
fsq C++
Garvit244 Python
gouthampradhan Java
halfrost Go
haoel C++
JoshCrozier JS
keineahnung2345 C++
lkwq007 Python
lzl124631x C++
suxrobGM C#
varunu28 Java
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, Python
LeetcodeHelp C++, Java, Python
MemoryLimitExceeded Python, C++
Progiez C++, Java, Python
BigEggStudy C#
black-shadows C++, C++
charles-wangkai Java
DimitrisJim C
everthis JavaScript
fsq C++
Garvit244 Python
gouthampradhan Java
halfrost Go
haoel C++
JoshCrozier JavaScript
keineahnung2345 C++
lkwq007 Python
lzl124631x C++
suxrobGM C#
varunu28 Java
35 links | 22 authors | 8 languages

Videos

5 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

1 similar problem

Solved On The Same Day

11 solutions   December 19, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality