Problem 566

Abstract / Summary

Given a matrix and new dimensions, return the reshaped matrix if possible, keeping elements in row traversal order.

Note

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

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
15 lines | 480 bytes | submitted September 19, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 63% (600k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Matrix
  • Simulation
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 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.

written by openai gpt

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.

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 | μ = 7.26 | σ = 1.14

Complexity Analysis

not analyzed yet

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 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++
39 links | 24 authors | 10 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

1 easy 6 medium 2 hard
10 solutions   September 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