algoadvance

Leetcode 867. Transpose Matrix

Problem Statement

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.

For example, the transpose of a matrix:

[
  [1,2,3],
  [4,5,6],
  [7,8,9]
]

is

[
  [1,4,7],
  [2,5,8],
  [3,6,9]
]

Clarifying Questions

1. Input Constraints: Are the elements of the matrix bounded by any value range?
   • There are no specific constraints provided, so we can assume they are integers within a typical range.
2. Matrix Size: Can the matrix be non-square (i.e., different number of rows and columns)?
   • Yes, the matrix can be non-square.
3. Edge Cases: Can the input matrix be empty or contain a single element?
   • The matrix can contain any form of input that is within the problem’s constraints. An empty matrix would be an edge case to handle.

Strategy

1. Create a New Matrix: Initialize a new matrix transpose with the dimensions swapped — if the original matrix is m x n, the new matrix will be n x m.

2. Iterate and Assign Values: Iterate over the original matrix, and for each element at position (i,j), place it in the new matrix at position (j,i).

3. Return Result: Return the newly created transposed matrix.

Code

public class Solution {
    public int[][] transpose(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] transpose = new int[n][m];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                transpose[j][i] = matrix[i][j];
            }
        }
        
        return transpose;
    }
}

Time Complexity

• Time Complexity: O(m * n)
  • We iterate over every element of the m x n matrix once, making a single operation for each. Thus, the complexity is proportional to the number of elements in the matrix.
• Space Complexity: O(m * n)
  • The space complexity is also O(m * n) because we are creating a new matrix of the same number of elements as the input matrix but with swapped dimensions.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?