easy Transpose Matrix

Problem Statement

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

In the transpose matrix, the first row of the original matrix becomes the first column, the second row becomes the second column, and so on.

Examples

• Example 1:
  • Input:

[[1,2],
 [3,4]]

• Expected Output:

[[1,3],
 [2,4]]

• Justification: The first row [1,2] becomes the first column [1,3], and the second row [3,4] becomes the second column [2,4].

• Example 2:

  • Input:

[[5,6,7],
 [8,9,10],
 [11,12,13]]

• Expected Output:

[[5,8,11],
 [6,9,12],
 [7,10,13]]

• Justification: The matrix is rearranged such that each row becomes a column in the transposed matrix.

• Example 3:

  • Input:

[[14,15,16,17],
 [18,19,20,21],
 [22,23,24,25],
 [26,27,28,29]]

• Expected Output:

[[14,18,22,26],
 [15,19,23,27],
 [16,20,24,28],
 [17,21,25,29]]

• Justification: Similar to the previous examples, each row of the original matrix is transformed into a column in the transposed matrix.

Solution

To solve this problem, we'll create a new matrix where the number of rows equals the number of columns in the original matrix, and vice versa. The key idea is to iterate through each element of the original matrix and assign it to the appropriate position in the new matrix. This approach ensures that all elements are moved to their correct positions in the transposed matrix.

We believe this method is effective because it directly addresses the definition of matrix transposition by rearranging elements based on their indices. It's efficient as it requires only a single pass through the original matrix, making it both straightforward and suitable for large matrices.

Step-by-step Algorithm

1. Initialize a new matrix for the transposed result. The dimensions of this new matrix will be the transpose of the original matrix's dimensions (i.e., if the original matrix has dimensions n x m, the transposed matrix will have dimensions m x n).

2. Iterate through the rows of the original matrix. Use a loop that iterates from 0 to n - 1, where n is the number of rows in the original matrix.

3. Iterate through the columns of the original matrix within each row iteration. Use a nested loop that iterates from 0 to m - 1, where m is the number of columns in the original matrix.

4. Assign each element to its new position in the transposed matrix. During the nested iteration, for each element at position (i, j) in the original matrix, assign its value to position (j, i) in the new transposed matrix.

5. Return the transposed matrix as the output of the function.

Algorithm Walkthrough

Let's consider the input: matrix = [[5,6,7],[8,9,10],[11,12,13]]

Let's walk through the algorithm step by step using the provided example matrix.

1. Initialize the transposed matrix: Since the input matrix has dimensions 3 x 3 (3 rows and 3 columns), we initialize a new matrix with the same dimensions 3 x 3, as the input matrix is square. This new matrix starts as [[0,0,0],[0,0,0],[0,0,0]].

2. Iterate through the rows of the original matrix:

   • First iteration (i = 0): The focus is on the first row [5,6,7].

     • Nested iteration for columns:
       • j = 0: The first element (5) is placed in the transposed matrix at (0, 0). The transposed matrix now is [[5,0,0],[0,0,0],[0,0,0]].
       • j = 1: The second element (6) is placed in the transposed matrix at (1, 0). The transposed matrix now is [[5,0,0],[6,0,0],[0,0,0]].
       • j = 2: The third element (7) is placed in the transposed matrix at (2, 0). The transposed matrix now is [[5,0,0],[6,0,0],[7,0,0]].

   • Second iteration (i = 1): The focus shifts to the second row [8,9,10].

     • Nested iteration for columns:
       • j = 0: The first element (8) is placed in the transposed matrix at (0, 1). The transposed matrix now is [[5,8,0],[6,0,0],[7,0,0]].
       • j = 1: The second element (9) is placed in the transposed matrix at (1, 1). The transposed matrix now is [[5,8,0],[6,9,0],[7,0,0]].
       • j = 2: The third element (10) is placed in the transposed matrix at (2, 1). The transposed matrix now is [[5,8,0],[6,9,0],[7,10,0]].

   • Third iteration (i = 2): Now looking at the third row [11,12,13].

     • Nested iteration for columns:
       • j = 0: The first element (11) is placed in the transposed matrix at (0, 2). The transposed matrix now is [[5,8,11],[6,9,0],[7,10,0]].
       • j = 1: The second element (12) is placed in the transposed matrix at (1, 2). The transposed matrix now is [[5,8,11],[6,9,12],[7,10,0]].
       • j = 2: The third element (13) is placed in the transposed matrix at (2, 2). The transposed matrix is now complete as [[5,8,11],[6,9,12],[7,10,13]].

3. Return the transposed matrix: The final step is to return the fully transposed matrix, which in this case is [[5,8,11],[6,9,12],[7,10,13]].

Code

public class Solution {

  public int[][] transpose(int[][] matrix) {
    // Determine the number of rows and columns in the input matrix.
    int rows = matrix.length;
    int cols = matrix[0].length;
    // Initialize the transposed matrix with switched dimensions.
    int[][] transposedMatrix = new int[cols][rows];

    // Iterate through each element of the matrix.
    for (int i = 0; i < rows; i++) {
      for (int j = 0; j < cols; j++) {
        // Assign the element to its new position in the transposed matrix.
        transposedMatrix[j][i] = matrix[i][j];
      }
    }

    // Return the transposed matrix.
    return transposedMatrix;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    // Test the transpose method with three example matrices.
    // Example 1: 2x2 matrix
    int[][] example1 = { { 1, 2 }, { 3, 4 } };
    // Example 2: 3x3 matrix
    int[][] example2 = { { 5, 6, 7 }, { 8, 9, 10 }, { 11, 12, 13 } };
    // Example 3: 4x4 matrix
    int[][] example3 = {
      { 14, 15, 16, 17 },
      { 18, 19, 20, 21 },
      { 22, 23, 24, 25 },
      { 26, 27, 28, 29 },
    };

    printMatrix(solution.transpose(example1));
    printMatrix(solution.transpose(example2));
    printMatrix(solution.transpose(example3));
  }

  private static void printMatrix(int[][] matrix) {
    // Helper method to print the matrices.
    for (int[] row : matrix) {
      for (int val : row) {
        System.out.print(val + " ");
      }
      System.out.println();
    }
  }
}

Complexity Analysis

Time Complexity

The time complexity is , where n is the number of rows and m is the number of columns in the input matrix. This is because each element in the n x m matrix is visited exactly once to place it in its new position in the transposed matrix.

Space Complexity

The space complexity is as well, due to the creation of a new transposed matrix of size n x m. No additional space besides the output matrix is used, so the space complexity directly corresponds to the size of the output.

🎯 STRICT STANDOUT — Solution Transpose Matrix

1. Why / judgment

Allocate ans[n][m]; double loop r,c set ans[c][r]=A[r][c]. Correct by definition of transpose.

2. Big-O derivation (K11)

Loops mn times O(mn). Space O(mn) for answer (required).
Trace 2×3 → 3×2 as expected.

3. Pattern + when-NOT (K12)

Name: DIRECT CONSTRUCTION

Recognition: transpose.

When-NOT: In-place square: for i for j>i swap.

4. Edge hand-run (K13)

1×1 identity.
row vector.

5. Interviewer follow-ups (model answers)

Q1. Off-by-one shape?
A: ans rows = A cols; ans cols = A rows.

Q2. Alias if caller expects mutate?
A: API usually returns new matrix.

Q3. Parallelize?
A: Embarrassingly parallel per element.

6. Short drills

Drill: square in-place swap version.
Drill: prove (A^T)^T=A by index chase.