algoadvance

Leetcode 867. Transpose Matrix

Problem Statement

The problem “Transpose Matrix” can be found as problem number 867 on LeetCode. The task is as follows:

Given a 2D integer array matrix, return the transpose of matrix.

The transpose of a matrix is the matrix flipped over its main diagonal, switching the matrix’s row and column indices.

Example:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[1,4,7],[2,5,8],[3,6,9]]

Input: matrix = [[1,2,3],[4,5,6]]
Output: [[1,4],[2,5],[3,6]]

Clarifying Questions

  1. What size can the matrix be?
    • The matrix can have any size within reasonable limits (e.g., (1 \leq matrix.length, matrix[i].length \leq 1000)).
  2. What type of elements does the matrix contain?
    • The elements are integers.
  3. Is it given that the input matrix is always rectangular?
    • Yes, the input matrix is always rectangular, meaning all rows have the same number of columns.
  4. Can the matrix have negative numbers?
    • Yes, the matrix can contain any integer values, including negative numbers.

Strategy

To transpose a matrix, we need to swap the rows and columns of the input matrix. This means that the element at position [i][j] in the original matrix will be at position [j][i] in the transposed matrix.

Steps:

  1. Determine the dimensions of the input matrix.
  2. Initialize a new matrix with flipped dimensions (number of rows becomes the number of columns and vice versa).
  3. Populate the new matrix by assigning transpose[j][i] = matrix[i][j].
  4. Return the transposed matrix.

Time Complexity

The time complexity for this operation is (O(m \times n)), where m is the number of rows and n is the number of columns in the input matrix. This is because each element must be accessed once to be placed in the transposed matrix.

Code

#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> transpose(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> transposed(n, vector<int>(m));
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                transposed[j][i] = matrix[i][j];
            }
        }
        
        return transposed;
    }
};

Detailed Explanation of the Code

  1. Determine the dimensions of the matrix:
    • m is the number of rows in the input matrix.
    • n is the number of columns in the input matrix.
  2. Create a new matrix transposed with dimensions n x m.
  3. Use nested loops to iterate over each element in the original matrix:
    • The outer loop iterates over the rows i.
    • The inner loop iterates over the columns j.
    • Assign the element matrix[i][j] to transposed[j][i].
  4. Finally, return the transposed matrix.

This solution efficiently transposes the input matrix with a clear O(m * n) time complexity.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI