Return the transpose of a square image

You're working on a game engine at Blizzard when a colleague asks you to transform a sprite's pixel data so that its rows become columns. "Just transpose it," they say casually, as if everyone has a matrix transpose function in their back pocket. This problem, also known as "Transpose Matrix" on other interview platforms, is one of those foundational matrix operations that shows up in image processing, linear algebra, and technical interviews alike. It tests your ability to work with 2D arrays and understand coordinate transformations.

TL;DR

To transpose a square matrix, create a new matrix of the same size and copy each element from position [row][col] to position [col][row]. Use nested loops to iterate through every element, swapping the row and column indices as you write to the output. This runs in O(m * n) time and O(m * n) space. The diagonal elements stay in place since swapping their indices produces the same position.

Why This Problem Matters

Matrix transpose is one of those operations that sounds trivial until you actually sit down to implement it. It's a great warm-up problem for matrix manipulation interviews, and the pattern of swapping row and column indices appears in many other problems like rotating an image 90 degrees, reflecting a matrix, or converting between row-major and column-major storage. If you can transpose a matrix cleanly, you've demonstrated comfort with 2D array indexing, which is a prerequisite for harder grid-based problems.

Understanding the Problem

Given a square image represented as a 2D array of integers (pixel values between 0 and 255), return a new 2D array that is the transpose of the original. The transpose flips a matrix over its main diagonal, turning rows into columns and columns into rows.

Here is the example from the problem:

transpose([[255,0],[255,255]]) returns [[255,255],[0,255]]

Let's visualize that. The original image:

After transposing, the pixel at [0][1] (value 0, purple) swaps with the pixel at [1][0] (value 255, green):

Notice that the diagonal elements at [0][0] and [1][1] (both 255, blue) stayed in place. This is always true for transpose.

Edge Cases to Consider

1. Single pixel (1x1 matrix): Already its own transpose, return as-is
2. 2x2 matrix: The simplest non-trivial case, good for tracing through your algorithm
3. Symmetric matrices: If the matrix equals its transpose, the output is identical to the input

The Key Insight

The transpose operation has one simple rule: every element at position [row][col] moves to position [col][row]. That's it. The row index becomes the column index, and vice versa.

Let's see this with a 3x3 matrix. Here is the original:

And the transposed result:

Look at how each element moved. The value 2 was at [0][1] (purple) and moved to [1][0]. The value 4 was at [1][0] (orange) and moved to [0][1]. Meanwhile, the diagonal elements 1, 5, and 9 (blue) stayed exactly where they were.

Why the Diagonal Stays Put

The main diagonal consists of all positions where the row index equals the column index: [0][0], [1][1], [2][2], and so on. When you swap the indices for a diagonal element, [i][i] becomes [i][i]. Nothing changes. This diagonal acts as the mirror line for the entire transpose operation.

The green-highlighted cells above sit on the main diagonal. Every other element reflects across this line during transposition.

Solution Approach

The algorithm is straightforward:

1. Determine the size of the square matrix
2. Create a new output matrix of the same dimensions
3. For each position [row][col], copy the value from image[col][row] into transposed[row][col]
4. Return the new matrix

We use a fresh matrix rather than modifying in-place because swapping elements in a single matrix without careful ordering would overwrite values we still need to read.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public int[][] transpose(int[][] image) {
    // Get the size of the square matrix
    int size = image.length;

    // Create an output array of the same dimensions
    int[][] transposed = new int[size][size];

    // Iterate over every position and swap row/column indices
    for (int row = 0; row < size; row++) {
      for (int col = 0; col < size; col++) {
        transposed[row][col] = image[col][row];
      }
    }

    return transposed;
  }
}

Let's trace through this with [[1,2],[3,4]]:

Iteration (row=0, col=0): transposed[0][0] = image[0][0] = 1 (diagonal, stays the same)

Iteration (row=0, col=1): transposed[0][1] = image[1][0] = 3 (was in row 1, now in row 0)

Iteration (row=1, col=0): transposed[1][0] = image[0][1] = 2 (was in row 0, now in row 1)

Iteration (row=1, col=1): transposed[1][1] = image[1][1] = 4 (diagonal, stays the same)

The result:

Values 2 (purple) and 3 (green) have swapped positions, while 1 and 4 (blue, on the diagonal) remained in place.

Complexity Analysis

Time Complexity: O(m * n)

We visit every element in the matrix exactly once. For a square matrix of size n, this is O(n^2). Each visit involves a constant-time array read and write, so the total work scales linearly with the number of elements.

Space Complexity: O(m * n)

We allocate a new matrix of the same dimensions as the input. This is necessary to avoid overwriting values during the swap. For a square matrix, this is O(n^2) additional space.

Could We Do Better on Space?

For square matrices, you can transpose in-place with O(1) extra space by swapping matrix[i][j] with matrix[j][i] for all positions where i is strictly less than j. This avoids double-swapping and eliminates the need for a second array. However, the two-array approach is cleaner to reason about and less error-prone, which matters in an interview setting.

Common Pitfalls

1. Confusing source and destination indices: Writing transposed[row][col] = image[row][col] just copies the matrix. The swap is image[col][row], not image[row][col].

2. Modifying the input array: If you try to transpose in-place without being careful about which half of the matrix you process, you will overwrite values before reading them.

3. Mixing up transpose and rotation: A 90-degree rotation is transpose followed by reversing each row. Transpose alone does not rotate.

Interview Tips

When solving this in an interview:

1. Draw it out: Sketch a small 2x2 or 3x3 matrix and show the interviewer how elements move. This makes the [row][col] to [col][row] mapping immediately clear.

2. Mention the in-place alternative: Even if you implement the two-array version, noting that square matrices can be transposed in O(1) space shows depth of understanding.

3. Connect to related problems: If the interviewer asks follow-ups about rotating an image, you can explain that rotation is just transpose plus row reversal.

4. Watch for non-square matrices: This problem specifies a square image, but if the interviewer generalizes to rectangular matrices, the dimensions of the output change. An m-by-n matrix transposes to an n-by-m matrix.

Key Takeaways

• Transpose swaps every element from [row][col] to [col][row], with diagonal elements staying fixed.
• Creating a new output matrix avoids the complexity of in-place swapping and is the safest approach during interviews.
• The pattern of nested loops over a 2D array with index manipulation is foundational for matrix problems like rotation, reflection, and spiral traversal.
• For square matrices, in-place transpose is possible by iterating only over the upper triangle and swapping across the diagonal.
• Always trace through a small example (2x2 or 3x3) to verify your index mapping before coding.

Solutions in Other Languages

Python

class Solution:
    def transpose(self, image):
        size = len(image)
        transposed = [[0 for _ in range(size)] for _ in range(size)]
        for row in range(size):
            for col in range(size):
                transposed[row][col] = image[col][row]
        return transposed

JavaScript

class Solution {
  transpose(image) {
    const size = image.length;
    const transposed = [...Array(size)].map(_ => Array(size));
    for (let row = 0; row < size; row++) {
      for (let col = 0; col < size; col++) {
        transposed[row][col] = image[col][row];
      }
    }
    return transposed;
  }
}

TypeScript

class Solution {
  transpose(image: number[][]): number[][] {
    const size = image.length;
    const transposed: number[][] = Array.from({ length: size }, () => new Array(size));
    for (let row = 0; row < size; row++) {
      for (let col = 0; col < size; col++) {
        transposed[row][col] = image[col][row];
      }
    }
    return transposed;
  }
}

C++

#include <vector>

class Solution {
public:
  std::vector<std::vector<int>> transpose(std::vector<std::vector<int>> &image) {
    int size = image.size();
    std::vector<std::vector<int>> transposed(size, std::vector<int>(size));
    for (int row = 0; row < size; row++) {
      for (int col = 0; col < size; col++) {
        transposed[row][col] = image[col][row];
      }
    }
    return transposed;
  }
};

Go

func Transpose(image [][]int) [][]int {
    size := len(image)
    transposed := make([][]int, size)
    for i := range transposed {
        transposed[i] = make([]int, size)
    }
    for row := 0; row < size; row++ {
        for col := 0; col < size; col++ {
            transposed[row][col] = image[col][row]
        }
    }
    return transposed
}

Scala

class Solution {
  def transpose(image: Array[Array[Int]]): Array[Array[Int]] = {
    val size = image.length
    val transposed = Array.ofDim[Int](size, size)
    for (row <- 0 until size) {
      for (col <- 0 until size) {
        transposed(row)(col) = image(col)(row)
      }
    }
    transposed
  }
}

Kotlin

class Solution {
    fun transpose(image: Array<IntArray>): Array<IntArray> {
        val size = image.size
        val transposed = Array(size) { IntArray(size) }
        for (row in 0 until size) {
            for (col in 0 until size) {
                transposed[row][col] = image[col][row]
            }
        }
        return transposed
    }
}

Swift

class Solution {
    func transpose(_ image: [[Int]]) -> [[Int]] {
        let size = image.count
        var transposed = Array(repeating: Array(repeating: 0, count: size), count: size)
        for row in 0..<size {
            for col in 0..<size {
                transposed[row][col] = image[col][row]
            }
        }
        return transposed
    }
}

Ruby

class Solution
  def transpose(image)
    size = image.length
    transposed = Array.new(size) { Array.new(size) }
    (0...size).each do |row|
      (0...size).each do |col|
        transposed[row][col] = image[col][row]
      end
    end
    transposed
  end
end

Rust

pub fn transpose(image: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let size = image.len();
    let mut transposed = vec![vec![0; size]; size];
    for row in 0..size {
        for col in 0..size {
            transposed[row][col] = image[col][row];
        }
    }
    transposed
}

C#

public class Solution {
    public int[][] Transpose(int[][] image) {
        int size = image.Length;
        int[][] transposed = new int[size][];
        for (int row = 0; row < size; row++) {
            transposed[row] = new int[size];
            for (int col = 0; col < size; col++) {
                transposed[row][col] = image[col][row];
            }
        }
        return transposed;
    }
}

Dart

class Solution {
  List<List<int>> transpose(List<List<int>> image) {
    int size = image.length;
    List<List<int>> transposed = List.generate(size, (i) => List.filled(size, 0));
    for (int row = 0; row < size; row++) {
      for (int col = 0; col < size; col++) {
        transposed[row][col] = image[col][row];
      }
    }
    return transposed;
  }
}

PHP

class Solution {
    public function transpose(array $image): array {
        $size = count($image);
        $transposed = array_fill(0, $size, array_fill(0, $size, 0));
        for ($row = 0; $row < $size; $row++) {
            for ($col = 0; $col < $size; $col++) {
                $transposed[$row][$col] = $image[$col][$row];
            }
        }
        return $transposed;
    }
}

Practice Makes Perfect

Once you're comfortable with matrix transpose, try these related problems to strengthen your 2D array skills:

• Rotate an image 90 degrees (transpose + reverse rows)
• Flip an image on its horizontal axis
• Zero out rows and columns
• Matrix spiral traversal

Remember, consistent practice is the key to succeeding in coding interviews. This problem and thousands of others are available on Firecode, where over 50,000 users have successfully prepared for technical interviews and landed six and seven-figure jobs at top tech companies. Whether you're just starting or preparing for your dream job, mastering matrix fundamentals like this will set you up for success.

Happy coding, and may all your matrices transpose cleanly!