Transpose Matrix

EASY✓ CHIP-TIMEDLC #867 — FULL STATEMENT ↗

The drill: Flip a grid across its main diagonal so every row becomes a column and every column becomes a row — a matrix that was rows×cols comes back cols×rows, with matrix[i][j] landing at [j][i].

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A 2D grid of numbers arrives with some number of rows and some number of columns, and the task is to produce its mirror image across the main diagonal.

Every value that lived at row i, column j moves to row j, column i in the output — rows become columns and columns become rows, so a grid that started rows-by-cols comes back cols-by-rows instead.

The output is a brand-new grid built from the input's values in their new positions; the original grid's own shape and contents are simply the source data for that rearrangement.

EX 01

matrix = [[1, 2], [3, 4]]

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

SQUARE 2X2

EX 02

matrix = [[1, 2, 3], [4, 5, 6]]

→ [[1, 4], [2, 5], [3, 6]]

WIDE RECTANGLE BECOMES TALL

EX 03

matrix = [[1], [2], [3]]

→ [[1, 2, 3]]

SINGLE COLUMN BECOMES SINGLE ROW

grids run up to a few hundred rows and columns
cell values are integers, positive, negative, or zero
rows need not equal columns — rectangular grids are expected
the output's dimensions are swapped from the input's

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Every output cell has a fixed source: the value at output row j, column i, always came from input row i, column j. Once that mapping is clear, the shape of the loop follows directly.

HINT 2 THE STRUCTURE

The output's dimensions are known before touching a single cell — cols×rows instead of rows×cols — so nothing about its shape needs to be discovered as you go.

HINT 3 ONE STEP FROM THE ANSWER

Allocate the cols×rows result up front and, for every input cell (i, j), drop matrix[i][j] straight into result[j][i]. One pass, one direct write per cell, no growing containers.

COACH'S BOARD — THE PATTERN, STEP BY STEP

PRE-SIZED, DIRECT SWAPPATTERN · DIRECT MIRRORED WRITEmatrix = [[1,2,3],[4,5,6]]

STEP 1

Input is 2×3: [[1,2,3],[4,5,6]]. Output will be 3×2 — allocate it empty and fill by mirroring across the diagonal.

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/transpose-matrix.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
        rows, cols = len(matrix), len(matrix[0])
        result = [[0] * rows for _ in range(cols)]
        for i in range(rows):
            for j in range(cols):
                result[j][i] = matrix[i][j]   # direct mirrored write, no growth
        return result

TIME O(ROWS·COLS)SPACE O(1) EXTRAPYTHON · RACE PACE · 8 LN

class Solution:
    def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
        rows, cols = len(matrix), len(matrix[0])
        result = [[] for _ in range(cols)]
        for j in range(cols):               # walk column by column...
            for i in range(rows):
                result[j].append(matrix[i][j])   # ...appending down each one
        return result

TIME O(ROWS·COLS)SPACE O(ROWS·COLS)PYTHON · TRAINING PACE · 8 LN

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

TIME O(ROWS·COLS)SPACE O(1) EXTRAJAVA · RACE PACE · 12 LN

class Solution {
    public int[][] transpose(int[][] matrix) {
        int rows = matrix.length, cols = matrix[0].length;
        List<List<Integer>> columns = new ArrayList<>();
        for (int j = 0; j < cols; j++) {
            columns.add(new ArrayList<>());
        }
        for (int j = 0; j < cols; j++) {
            for (int i = 0; i < rows; i++) {
                columns.get(j).add(matrix[i][j]);
            }
        }

        int[][] result = new int[cols][rows];
        for (int j = 0; j < cols; j++) {
            for (int i = 0; i < rows; i++) {
                result[j][i] = columns.get(j).get(i);
            }
        }
        return result;
    }
}

TIME O(ROWS·COLS)SPACE O(ROWS·COLS)JAVA · TRAINING PACE · 22 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED