Python 0566.py
class Solution:
def matrixReshape(self, mat: List[List[int]], r: int, c: int) -> List[List[int]]:
width = len(mat[0])
height = len(mat)
if width * height != r * c:
return mat
result = []
for y in range(height):
for x in range(width):
if not result or len(result[-1]) == c:
result.append([])
result[-1].append(mat[y][x])
return result
Difficulty
and has an acceptance rate of about 63% (600k+ submissions).
Typical patterns to solve this problem:
- Array
- Matrix
- Simulation
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 provided Solution class implements a method matrixReshape that transforms a two-dimensional list mat into a new matrix with a specified number of rows r and columns c. The transformation preserves the original element order when read row-wise. If the total number of elements does not match the requested shape, the original matrix is returned unchanged.
Core Logic
The method begins by determining the dimensions of the input matrix.
width = len(mat[0])
height = len(mat)
width holds the number of columns in the first row, while height records the number of rows. This information is essential for both the feasibility check and the subsequent element traversal.
A feasibility check follows, comparing the product of the original dimensions with the product of the target dimensions.
if width * height != r * c:
return mat
When the element counts differ, the method exits early, returning the input matrix unchanged. This early return prevents unnecessary work and guarantees that the output shape is always valid.
If the reshape is possible, the method constructs the new matrix. An empty list result is created to accumulate rows of the reshaped matrix.
result = []
Two nested loops iterate over the original matrix in row-major order.
for y in range(height):
for x in range(width):
if not result or len(result[-1]) == c:
result.append([])
result[-1].append(mat[y][x])
The outer loop iterates over each original row index y, while the inner loop walks through each column index x. For every element mat[y][x], the code checks whether a new row needs to be started. The condition not result handles the very first element, ensuring that result contains at least one sub-list before appending. The second part of the condition, len(result[-1]) == c, detects when the most recent row has reached the target column count c. In either case, a fresh empty list is appended to result, representing a new row in the reshaped matrix.
After guaranteeing that a suitable row exists, the current element is appended to the last row:
result[-1].append(mat[y][x])
When the loops finish, result contains exactly r rows, each of length c, preserving the original element order. The method then returns result.
return result
Edge Cases Handled
The primary edge case addressed is a mismatch between the total number of elements in the original matrix and the requested shape. By checking width * height != r * c, the method safely returns the original matrix when a reshape would either truncate or require padding, thereby avoiding index errors or incomplete rows.
Another subtle edge case is the handling of the very first element. The condition not result ensures that the code creates the initial row before any element is added, preventing an attempt to access result[-1] when result is still empty.
Performance Optimizations
The implementation performs a single pass over the input matrix, visiting each element exactly once. This linear traversal eliminates the need for intermediate flattening or slicing operations, reducing both memory overhead and execution time.
Row creation is deferred until necessary. By checking the length of the most recent row (len(result[-1]) == c) before appending a new row, the code avoids pre-allocating a full list of rows. This on-demand allocation aligns with the natural flow of data and keeps the memory footprint minimal.
Appending to Python lists (result.append([]) and result[-1].append(...)) leverages the amortized O(1) behavior of list appends, ensuring that the construction of the reshaped matrix remains efficient even for large inputs.
Overall, the method balances clarity with efficiency, delivering a correct reshape operation while minimizing auxiliary data structures and redundant passes.
ELI5 - Simplified Explanation
Imagine a big box of colorful building blocks arranged in a flat rectangle. Some rows are long and some are short, but all the blocks are tucked inside neatly.
The code starts by checking if the total number of blocks in the rectangle matches the total number of spots in a new shape that is being requested. If the number of blocks is different, it is impossible to rebuild the shape, so it chooses to keep the blocks exactly where they are.
If the number of blocks is the same, it begins a fun process of moving them one by one. It looks at every single block in the original rectangle, starting from the top left corner and moving across each row just like reading a storybook.
As it finds each block, it puts that block on a new pile. When a row in the new shape is full, it starts a brand new row right underneath. It repeats this until every block has been moved from the old rectangle into the new, specially shaped one. It is just like pouring your blocks from a wide tray into a tall, thin container until everything is tucked away in the new arrangement.
Code Quality
Complexity Analysis
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 | Rust | Go | C | TS | ||||
| LeetcodeHelp | C++ | Java | Python | ||||||||
| Progiez | C++ | Java | Python | ||||||||
| github | BigEggStudy | C# | |||||||||
| black-shadows | C++ | ||||||||||
| charles-wangkai | Java | ||||||||||
| DimitrisJim | C | ||||||||||
| everthis | JS | ||||||||||
| fartem | Ruby | ||||||||||
| fengvyi | C++ | ||||||||||
| halfrost | Go | ||||||||||
| JoshCrozier | JS | ||||||||||
| keineahnung2345 | C++ | ||||||||||
| Krazune | C++ | ||||||||||
| linouk23 | C++ | ||||||||||
| lkwq007 | Python | ||||||||||
| ruoru | Rust | ||||||||||
| suxrobGM | C# | ||||||||||
| varunu28 | Java | ||||||||||
| vthwang | Java | ||||||||||
| YuriSpiridonov | Python | ||||||||||
| zfang399 | C++ | ||||||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||||||
| WalkCCC | C++, Python, Java | ||||||||||
| leetcode.ca | C, C++, Go, Java, Python, Rust, TypeScript | ||||||||||
| LeetcodeHelp | C++, Java, Python | ||||||||||
| Progiez | C++, Java, Python | ||||||||||
| BigEggStudy | C# | ||||||||||
| black-shadows | C++, C++ | ||||||||||
| charles-wangkai | Java | ||||||||||
| DimitrisJim | C | ||||||||||
| everthis | JavaScript | ||||||||||
| fartem | Ruby | ||||||||||
| fengvyi | C++ | ||||||||||
| halfrost | Go | ||||||||||
| JoshCrozier | JavaScript | ||||||||||
| keineahnung2345 | C++ | ||||||||||
| Krazune | C++ | ||||||||||
| linouk23 | C++ | ||||||||||
| lkwq007 | Python | ||||||||||
| ruoru | Rust | ||||||||||
| suxrobGM | C# | ||||||||||
| varunu28 | Java | ||||||||||
| vthwang | Java | ||||||||||
| YuriSpiridonov | Python | ||||||||||
| zfang399 | C++ |
Videos
Similar Problems
- problem 2022: Convert 1D Array Into 2D Array
Solved On The Same Day
- problem 594: Longest Harmonious Subsequence
- problem 324: Wiggle Sort II
- problem 386: Lexicographical Numbers
- problem 388: Longest Absolute File Path
- problem 390: Elimination Game
- problem 406: Queue Reconstruction by Height
- problem 491: Non-decreasing Subsequences
- problem 410: Split Array Largest Sum
- problem 472: Concatenated Words
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