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) ]
Difficulty
and has an acceptance rate of about 74% (100k+ submissions).
Typical patterns to solve this problem:
- Array
- Geometry
- Math
- Matrix
- Sorting
AI Disclaimer
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.
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.
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.
Code Quality
Complexity Analysis
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
Other Solutions
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 |
Videos
Similar Problems
- problem 2194: Cells in a Range on an Excel Sheet
Solved On The Same Day
- problem 944: Delete Columns to Make Sorted
- problem 1200: Minimum Absolute Difference
- problem 1252: Cells with Odd Values in a Matrix
- problem 1290: Convert Binary Number in a Linked List to Integer
- problem 419: Battleships in a Board
- problem 816: Ambiguous Coordinates
- problem 866: Prime Palindrome
- problem 926: Flip String to Monotone Increasing
- problem 962: Maximum Width Ramp
- problem 979: Distribute Coins in Binary Tree
Extra
- 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