Multi-dimensional array transposing

Question

I have a row-based multidimensional array:

/** [row][column]. */
public int[][] tiles;

I would like to transform this array to column-based array, like following:

/** [column][row]. */
public int[][] tiles;

...But I really don't know where to start

Solution 1

try this:

@Test
public void transpose() {
    final int[][] original = new int[][]{
            {1, 2, 3, 4},
            {5, 6, 7, 8},
            {9, 10, 11, 12}};

    for (int i = 0; i < original.length; i++) {
        for (int j = 0; j < original[i].length; j++) {
            System.out.print(original[i][j] + " ");
        }
        System.out.print("\n");
    }
    System.out.print("\n\n matrix transpose:\n");
    // transpose
    if (original.length > 0) {
        for (int i = 0; i < original[0].length; i++) {
            for (int j = 0; j < original.length; j++) {
                System.out.print(original[j][i] + " ");
            }
            System.out.print("\n");
        }
    }
}

output:

1 2 3 4 
5 6 7 8 
9 10 11 12 


 matrix transpose:
1 5 9 
2 6 10 
3 7 11 
4 8 12 

Solution 2

I saw that all of the answers create a new resultant matrix. This is simple:

matrix[i][j] = matrix[j][i];

However, you can also do this in-place, in case of square matrix.

// Transpose, where m == n
for (int i = 0; i < m; i++) {
    for (int j = i + 1; j < n; j++) {
        int temp = matrix[i][j];
        matrix[i][j] = matrix[j][i];
        matrix[j][i] = temp;
    }
}

This is better for larger matrices, where creating a new resultant matrix is wasteful in terms of memory. If its not square, you can create a new one with NxM dimensions and do the out of place method. Note: for in-place, take care of j = i + 1. It's not 0.

Solution 3

The following solution does in fact return a transposed array instead of just printing it and works for all rectangular arrays, not just squares.

public int[][] transpose(int[][] array) {
    // empty or unset array, nothing do to here
    if (array == null || array.length == 0)
        return array;

    int width = array.length;
    int height = array[0].length;

    int[][] array_new = new int[height][width];

    for (int x = 0; x < width; x++) {
        for (int y = 0; y < height; y++) {
            array_new[y][x] = array[x][y];
        }
    }
    return array_new;
}

you should call it for example via:

int[][] a = new int[][]{{1, 2, 3, 4}, {5, 6, 7, 8}};
for (int i = 0; i < a.length; i++) {
    System.out.print("[");
    for (int y = 0; y < a[0].length; y++) {
        System.out.print(a[i][y] + ",");
    }
    System.out.print("]\n");
}

a = transpose(a); // call
System.out.println();

for (int i = 0; i < a.length; i++) {
    System.out.print("[");
    for (int y = 0; y < a[0].length; y++) {
        System.out.print(a[i][y] + ",");
    }
    System.out.print("]\n");
}

which will as expected output:

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

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

Solution 4

a bit more generic way:

/**
 * Transposes the given array, swapping rows with columns. The given array might contain arrays as elements that are
 * not all of the same length. The returned array will have {@code null} values at those places.
 * 
 * @param <T>
 *            the type of the array
 * 
 * @param array
 *            the array
 * 
 * @return the transposed array
 * 
 * @throws NullPointerException
 *             if the given array is {@code null}
 */
public static <T> T[][] transpose(final T[][] array) {
    Objects.requireNonNull(array);
    // get y count
    final int yCount = Arrays.stream(array).mapToInt(a -> a.length).max().orElse(0);
    final int xCount = array.length;
    final Class<?> componentType = array.getClass().getComponentType().getComponentType();
    @SuppressWarnings("unchecked")
    final T[][] newArray = (T[][]) Array.newInstance(componentType, yCount, xCount);
    for (int x = 0; x < xCount; x++) {
        for (int y = 0; y < yCount; y++) {
            if (array[x] == null || y >= array[x].length) break;
            newArray[y][x] = array[x][y];
        }
    }
    return newArray;
}

Solution 5

If you want to go for in place transpose of a matrix(in which case row count = col count) you can so following in Java

public static void inPlaceTranspose(int [][] matrix){

    int rows = matrix.length;
    int cols = matrix[0].length;

    for(int i=0;i<rows;i++){
        for(int j=i+1;j<cols;j++){
            matrix[i][j] = matrix[i][j] + matrix[j][i];
            matrix[j][i] = matrix[i][j] - matrix[j][i];
            matrix[i][j] = matrix[i][j] - matrix[j][i];
        }
    }
}

View more solutions

Comments

[ruakh]

That wouldn't work. You're probably thinking of C or C++; in Java, temp = tiles makes tiles and temp be references to the same array, and you've just totally b0rked it. :-P

[Jon Egeland]

What does it do wrong? Does it not compile? not copy the array? what?

[Jon Egeland]

That only prints out a change. It doesn't actually change the array.

[Kent]

no it didn't change the array, just showing how the loop worked

[yshavit]

Well, it doesn't compile -- tmp should be temp. Then also, you never instantiate temp (I assume tiles is coming in from some external source). But even fixing those, it turns [[1, 2], [3, 4]] into [[1, 2], [2, 4]]. And if the matrix is rectangular instead of square (ie, N x M instad of N x N), it'll throw an ArrayIndexOutOfBoundsException

[Alfredo Gallegos]

why is it j + 1 instead of 0? I guess it avoids redundant steps but my code started working after I initialized my j variable like you did instead of 0... besides that I had identical code

[Josh]

Please provide an explanation of this code and how it answers the question

[luk2302]

@AlfredoGallegos It is not "just" redundant, if you do extra steps you do extra swaps, that means if you swap twice you basically did not swap anything.