Transpose 2D Matrix in Java - Time & Space Complexity?

Question

Here's my algorithm / approach for transposing a 2D Matrix on the main diagonal.

Before:

a L M d 
b G c N 
H K e F 
I J O P 

After:

a b H I 
L G K J 
M c e O 
d N F P 

---

My code:

public class Matrix {

    static String[][] matrix = {

            {"a", "L", "M", "d"},
            {"b", "G", "c", "N"},
            {"H", "K", "e", "F"},
            {"I", "J", "O", "P"}
    };

    public void transpose(String[][] matrix) {
       String[][] transposedArray = new String [4][4];
       for (int row =0; row < 4; row ++) {
           for (int col = 0; col < 4; col++) {
               transposedArray[row][col] = matrix[col][row];  
           }
       }
    }
}

What is the time & space complexity of this approach?

Is there a better optimal solution?

Answer 1

I have three suggestions for you.

1. Instead of String, you can use char, less memory footprint than a String.
2. In the transpose method, I suggest that you return the array, since the method does nothing at the moment.

static char[][] matrix = {
   {'a', 'L', 'M', 'd'},
   {'b', 'G', 'c', 'N'},
   {'H', 'K', 'e', 'F'},
   {'I', 'J', 'O', 'P'}
};

public char[][] transpose(char[][] matrix) {
   char[][] transposedArray = new char [4][4];

   for (int row = 0; row < 4; row ++) {
      for (int col = 0; col < 4; col++) {
         transposedArray[row][col] = matrix[col][row];
      }
   }

   return transposedArray;
}

3. Since the matrix variable is static, I suggest that you also put the method static.

Refactored code

public static void main(String[] args) {
   System.out.println(Arrays.deepToString(transpose(matrix)));
}

static char[][] matrix = {
   {'a', 'L', 'M', 'd'},
   {'b', 'G', 'c', 'N'},
   {'H', 'K', 'e', 'F'},
   {'I', 'J', 'O', 'P'}
};

public static char[][] transpose(char[][] matrix) {
   char[][] transposedArray = new char [4][4];

   for (int row = 0; row < 4; row ++) {
      for (int col = 0; col < 4; col++) {
         transposedArray[row][col] = matrix[col][row];
      }
   }

   return transposedArray;
}

Answer 2

In addition to previous answers, which address valid points, I'd like to point out that your code is not scalable. If a matrix always has exactly 16 elements, time and space complexity are not really an issue, as they describe how the algorithm behaves at different scales.

You should figure out the row and column count of the matrix beforehand, and use these values when creating transposedArray and in your for loops.

As for time and space complexity, they both can be improved, as noted by Sharon Ben Asher in his answer. To go in further details, your algorithm performs n*m operations, or n² operations if m = n. Iterating on the upper half triangle reduces the number of operations to n * (n-1) / 2, which is a sizeable improvement by a factor 2. However, this would fail on a non-square matrix see the example below:

  input    |    expected  |   iteration on
           |     output   |  upper triangle
-------------------------------------------
a b c d    |     a e i    |     a e i d
e f g h    |     b f j    |     b f j h
i j k l    |     c g k    |     c g k l
           |     d h l    |

As you state that you are currently learning big O notation, note that the time complexity is still O(n²), as it is still the dominant term in the number of operations performed. The improvement is far from negligible, but it isn't represented in big O notation.

As of space complexity, swapping elements in place doesn't require allocating another n*m array to store the results of the operation. This means an improvement in terms of space complexity from O(n²) to O(1). This is great, especially with larger inputs. However, this also fails for non-square inputs, and means the input is mutated. If you happen to need the input in its original state, you'd have to transpose the matrix again.

Depending on the exact behavior you need, iterating on the full matrix or the upper triangle, and transposing in place or returning a transposed array can both be justified.

Finally, for integration purposes, your class could use some refactoring, most importantly to allow processing a matrix of any size.

Answer 3

Regarding time complexity, since your algorithm traverses the entire matrix once, it is working at O(n). this means the performance is affected in direct proportion to the size of the input (the matrix in this case). it is expected that a matrix with double the size (meaning four times the cell count) will perform 4 times worse than the original, and so forth.

Regarding space complexity, the algorithm allocates a new matrix the same size as the original. this also means that space requirements relate in direct proportion to the size of input. Here I have an improvement suggestion: the transformation can easily be done "in place" by iterating over half the matrix (triangular half, bordered by the diagonal) and swapping values of two cells. it also bares a small performance improvement - you need not touch the cells on the diagonal itself.