Transpose Matrix

NeetCode: Transpose Matrix · LeetCode: 867. Transpose Matrix · Difficulty: Easy

Given a 2D matrix, return its transpose: the matrix flipped over its main diagonal, so rows become columns. An m x n matrix becomes an n x m matrix, with result[j][i] = matrix[i][j].

Example

Text

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

A 2 x 3 matrix becomes a 3 x 2 one, so a new matrix is needed in general (only square matrices can be transposed in place). Every cell must be read and written once, so O(m * n) time is optimal, and both solutions below achieve it.

Brute force: allocate and fill with index loops

Create an n x m matrix (new int[n][m] is filled with zeros) and copy matrix[i][j] into result[j][i] with two nested loops.

Java

import java.util.Arrays;

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

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(Arrays.deepToString(s.transpose(new int[][] {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}})));
        System.out.println(Arrays.deepToString(s.transpose(new int[][] {{1, 2, 3}, {4, 5, 6}})));
        System.out.println(Arrays.deepToString(s.transpose(new int[][] {{1}, {2}, {3}})));
    }
}

Output

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

Time: O(m * n). Space: O(m * n) for the result.

Optimal: build each output row as a column with streams

The j-th row of the result is the j-th column of the input, that is, element j of every row. IntStream.range(0, n) produces the column indices. For each j, Arrays.stream(matrix).mapToInt(row -> row[j]).toArray() reads element j of every row into an int[]. The work is the same O(m * n), with no index arithmetic for the output and no zero-filled placeholder that is overwritten later. The streams add some object overhead compared with the plain loops.

Java

import java.util.Arrays;
import java.util.stream.IntStream;

class Solution {
    public int[][] transpose(int[][] matrix) {
        int n = matrix[0].length;
        return IntStream.range(0, n)
                .mapToObj(j -> Arrays.stream(matrix).mapToInt(row -> row[j]).toArray())
                .toArray(int[][]::new);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(Arrays.deepToString(s.transpose(new int[][] {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}})));
        System.out.println(Arrays.deepToString(s.transpose(new int[][] {{1, 2, 3}, {4, 5, 6}})));
        System.out.println(Arrays.deepToString(s.transpose(new int[][] {{1}, {2}, {3}})));
    }
}

Output

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

Time: O(m * n). Space: O(m * n) for the result.