566: Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n1. First, check if it is possible to reshape the matrix by comparing the 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n1. First, check if it is possible to reshape the matrix by comparing the product of the number of rows and columns of the original matrix with the product of the number of rows and columns of the desired reshaped matrix. If they are not equal, return the original matrix.\n2. Create a new matrix of size r x c using nested list comprehension.\n3. Traverse the original matrix in row-major order using a single index that starts at 0.\n4. For each element in the new matrix, calculate its row and column indices in the original matrix using integer division and modulo operations on the index, and then fill in the corresponding value from the original matrix.\n5. Increment the index by 1 for each iteration.\n6. Return the new matrix.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def matrixReshape(self, mat: List[List[int]], r: int, c: int) -> List[List[int]]:\n        # Check if it is possible to reshape the matrix\n        m, n = len(mat), len(mat[0])\n        if m * n != r * c:\n            return mat\n        \n        # Create a new matrix of size r x c\n        new_mat = [[0] * c for _ in range(r)]\n        \n        # Traverse the original matrix in row-major order\n        index = 0\n        for i in range(r):\n            for j in range(c):\n                # Fill in the values of the new matrix\n                row, col = divmod(index, n)\n                new_mat[i][j] = mat[row][col]\n                index += 1\n                \n        return new_mat\n\n```
['Array', 'Matrix', 'Simulation', 'Python', 'Python3']