LeetCode 566: Reshape the Matrix Solution in Python – A Step-by-Step Guide

What Is LeetCode 566: Reshape the Matrix?

In LeetCode 566: Reshape the Matrix, you’re given a 2D integer array mat representing a matrix, and two integers r and c for the desired number of rows and columns. Your task is to return a new matrix reshaped to r x c with the same elements in row-major order, or the original matrix if reshaping isn’t possible (i.e., if r * c doesn’t equal the original element count). For example, with mat = [[1,2],[3,4]], r = 1, c = 4, the result is [[1,2,3,4]]. This problem builds on LeetCode 88: Merge Sorted Array for array handling but focuses on transforming matrix dimensions.

Problem Statement

• Input: mat (List[List[int]])—2D integer matrix; r (int)—desired rows; c (int)—desired columns.
• Output: List[List[int]]—reshaped r x c matrix or original if impossible.
• Rules: Elements stay in row-major order; reshaping possible only if r c = original rows original cols.

Constraints

• 1 <= mat.length, mat[0].length <= 100
• -1000 <= mat[i][j] <= 1000
• 1 <= r, c <= 300

Examples

• Input: mat = [[1,2],[3,4]], r = 1, c = 4
• Output: [[1,2,3,4]]
• Reshape 2x2 (4 elements) to 1x4.
• Input: mat = [[1,2],[3,4]], r = 2, c = 4
• Output: [[1,2],[3,4]]
• 2x4 = 8 elements, original has 4, return original.
• Input: mat = [[1,2,3],[4,5,6]], r = 3, c = 2
• Output: [[1,2],[3,4],[5,6]]
• Reshape 2x3 to 3x2.

Understanding the Problem: Reshaping the Matrix

To solve LeetCode 566: Reshape the Matrix in Python, we need to transform a matrix into a new shape with r rows and c columns, keeping all elements in row-major order (left-to-right, top-to-bottom), but only if the total number of elements matches (r * c = m * n, where m and n are original dimensions). With matrix sizes up to 100x100 and target shapes up to 300x300, a brute-force copy could work, but we can optimize by flattening the matrix into a 1D list and reshaping it efficiently. We’ll explore:

• Best Solution (Flattening and Reshaping with Iteration): O(m n) time, O(m n) space—fast and clean.
• Alternative Solution (Brute-Force Element-by-Element Copy): O(m n) time, O(m n) space—simple but less intuitive.

Let’s dive into the flattening solution with a friendly breakdown!

Best Solution: Flattening and Reshaping with Iteration

Why Flattening Wins

The flattening and reshaping with iteration solution is the best for LeetCode 566 because it efficiently transforms the matrix in O(m * n) time and O(m * n) space by flattening the 2D matrix into a 1D list and then reshaping it into the target dimensions using a single pass, avoiding complex index mapping. It’s like unrolling a carpet of numbers and rolling it back into a new shape—all in one smooth motion!

How It Works

Think of this as a matrix-unroller:

• Step 1: Check Feasibility:
• If r c ≠ m n, return original matrix.
• Step 2: Flatten Matrix:
• Convert 2D mat into a 1D list of all elements in row-major order.
• Step 3: Reshape to Target:
• Iterate flattened list, fill new r x c matrix row-by-row.
• Step 4: Return Result:
• New reshaped matrix.
• Why It Works:
• Flattening preserves row-major order.
• Reshaping directly maps elements to new grid.

It’s like a matrix-shape shifter!

Step-by-Step Example

Example: mat = [[1,2],[3,4]], r = 1, c = 4

• Step 1: Check: 2 2 = 4, 1 4 = 4, feasible.
• Step 2: Flatten: [1, 2, 3, 4].
• Step 3: Reshape:
• New matrix: [[1, 2, 3, 4]] (1 row, 4 cols).
• Result: [[1,2,3,4]].

Example: mat = [[1,2,3],[4,5,6]], r = 3, c = 2

• Step 1: Check: 2 3 = 6, 3 2 = 6, feasible.
• Step 2: Flatten: [1, 2, 3, 4, 5, 6].
• Step 3: Reshape:
• Row 0: [1, 2].
• Row 1: [3, 4].
• Row 2: [5, 6].
• Result: [[1,2],[3,4],[5,6]].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

Copy codeclass Solution:
    def matrixReshape(self, mat: List[List[int]], r: int, c: int) -> List[List[int]]:
        # Step 1: Get original dimensions
        m = len(mat)
        n = len(mat[0])

        # Step 2: Check if reshaping is possible
        if m * n != r * c:
            return mat

        # Step 3: Flatten the matrix
        flat = []
        for i in range(m):
            for j in range(n):
                flat.append(mat[i][j])

        # Step 4: Reshape into r x c matrix
        reshaped = []
        k = 0
        for i in range(r):
            row = []
            for j in range(c):
                row.append(flat[k])
                k += 1
            reshaped.append(row)

        # Step 5: Return reshaped matrix
        return reshaped

• Lines 4-5: Get original rows (m) and cols (n).
• Lines 8-9: If element count mismatches, return original.
• Lines 12-15: Flatten matrix into 1D list.
• Lines 18-24: Build new r x c matrix from flat list.
• Line 27: Return reshaped matrix.
• Time Complexity: O(m * n)—single pass to flatten and reshape.
• Space Complexity: O(m * n)—storage for flat list and result.

It’s like a matrix-reshaping wizard!

Alternative Solution: Brute-Force Element-by-Element Copy

Why an Alternative Approach?

The brute-force element-by-element copy directly maps each element from the original matrix to the new matrix using index arithmetic, running in O(m * n) time and O(m * n) space. It’s simple but less intuitive, making it a good alternative for understanding basic index manipulation or when flattening feels indirect.

How It Works

Picture this as a matrix-element mover:

• Step 1: Check feasibility (r c = m n).
• Step 2: Create new r x c matrix.
• Step 3: Copy elements using index conversion.
• Step 4: Return new matrix.

It’s like a matrix-element shifter!

Step-by-Step Example

Example: mat = [[1,2],[3,4]], r = 1, c = 4

• Step 1: Check: 2 2 = 4, 1 4 = 4, feasible.
• Step 2: New matrix = [[0, 0, 0, 0]].
• Step 3: Copy:
• (0, 0) → (0, 0): 1.
• (0, 1) → (0, 1): 2.
• (1, 0) → (0, 2): 3.
• (1, 1) → (0, 3): 4.
• Result: [[1,2,3,4]].

Code for Brute-Force Approach

Copy codeclass Solution:
    def matrixReshape(self, mat: List[List[int]], r: int, c: int) -> List[List[int]]:
        m = len(mat)
        n = len(mat[0])

        if m * n != r * c:
            return mat

        reshaped = [[0] * c for _ in range(r)]
        for i in range(m):
            for j in range(n):
                # Convert 2D index to 1D position
                pos = i * n + j
                # Map to new r x c index
                new_i = pos // c
                new_j = pos % c
                reshaped[new_i][new_j] = mat[i][j]

        return reshaped

• Lines 6-7: Check feasibility.
• Line 9: Initialize r x c matrix.
• Lines 11-16: Map each element using index arithmetic.
• Line 18: Return reshaped matrix.
• Time Complexity: O(m * n)—single pass.
• Space Complexity: O(m * n)—new matrix.

It’s a brute-force matrix copier!

Comparing the Two Solutions

• Flattening (Best):
• Pros: O(m n), O(m n), intuitive.
• Cons: Extra flat list.
• Brute-Force (Alternative):
• Pros: O(m n), O(m n), direct.
• Cons: Index math complexity.

Flattening wins for clarity!

Additional Examples and Edge Cases

• [[1]], r = 1, c = 1: [[1]].
• [[1,2]], r = 2, c = 1: [[1],[2]].
• [[1,2]], r = 1, c = 1: [[1,2]] (impossible).

Flattening handles them all!

Complexity Recap

• Flattening: Time O(m n), Space O(m n).
• Brute-Force: Time O(m n), Space O(m n).

Flattening’s the elegance champ!

Key Takeaways

• Flattening: Shape shifting—learn at Python Basics!
• Brute-Force: Index mapping.
• Matrices: Reshaping is fun.
• Python: Flatten or map, your pick!

Final Thoughts: Reshape That Matrix!

LeetCode 566: Reshape the Matrix in Python is a delightful matrix challenge. Flattening and reshaping with iteration is your fast track, while brute-force offers a direct dive. Want more? Try LeetCode 88: Merge Sorted Array or LeetCode 48: Rotate Image. Ready to reshape? Head to Solve LeetCode 566 on LeetCode and transform that matrix today!