Column Major Traversal

The Problem

Given a 2D matrix, collect all of its elements in column-major order — top to bottom within each column, one column at a time — and return them as a flat list.

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

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

This is the mirror of row-major traversal. Instead of racing across rows, you race down columns.

Examples

Example 1 — 3×3 matrix

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

Example 2 — 2×4 matrix

Input:  [[3, 2, 1, 7], [0, 6, 3, 2]]
Output: [3, 0, 2, 6, 1, 3, 7, 2]

Example 3 — 1×1 matrix (edge case)

Input:  [[1]]
Output: [1]

Intuition

In row-major traversal, the column index (j) was in the inner loop — it moved fastest. Here we flip that completely:

Outer loop = columns (slow). Inner loop = rows (fast).

The outer loop picks a column. The inner loop walks from the top of that column to the bottom, collecting every element. Then the outer loop advances to the next column.

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart TB
  subgraph C0["Column 0"]
    n1["1"] --> n4["4"] --> n7["7"]
  end
  subgraph C1["Column 1"]
    n2["2"] --> n5["5"] --> n8["8"]
  end
  subgraph C2["Column 2"]
    n3["3"] --> n6["6"] --> n9["9"]
  end
  n7 -->|"next col →"| n2
  n8 -->|"next col →"| n3

Column-major traversal of a 3×3 matrix — drain each column top to bottom before moving to the next column.

Visit order annotated directly on the grid:

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
block-beta
  columns 3
  A["1  (1st)"] B["2  (4th)"] C["3  (7th)"]
  D["4  (2nd)"] E["5  (5th)"] F["6  (8th)"]
  G["7  (3rd)"] H["8  (6th)"] I["9  (9th)"]

Visit order in column-major traversal — the column index changes slowly (every 3 visits), while the row index changes on every visit.

The collected output:

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
block-beta
  columns 9
  A["1"] B["4"] C["7"] D["2"] E["5"] F["8"] G["3"] H["6"] I["9"]

Output — all 9 elements in column-major order as a flat list. Compare with row-major: [1, 2, 3, 4, 5, 6, 7, 8, 9].

The Approach

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart TB
  Start(["matrix with m rows, n cols"])
  Guard{"matrix is empty?"}
  Init["path = []"]
  ColLoop["for col in 0 → n-1"]
  RowLoop["for row in 0 → m-1"]
  Append["path.append(matrix[row][col])"]
  Done(["return path"])

  Start --> Guard
  Guard -->|"yes"| Done
  Guard -->|"no"| Init --> ColLoop --> RowLoop --> Append --> RowLoop
  RowLoop -->|"row exhausted"| ColLoop
  ColLoop -->|"col exhausted"| Done

Algorithm flow — the inner loop exhausts all rows in the current column before the outer loop advances to the next column.

The one critical change vs. row-major: col is the outer loop variable, row is the inner loop variable. Swap those two and you go from column-major to row-major.

Solution

from typing import List

class Solution:
    def column_major_traversal(self, matrix: List[List[int]]) -> List[int]:

        # Handle empty matrix
        if not matrix:
            return []

        rows: int = len(matrix)
        cols: int = len(matrix[0])
        path: List[int] = []

        # Outer loop: one step per column (slow dimension)
        for col in range(cols):
            # Inner loop: one step per row (fast dimension)
            for row in range(rows):
                path.append(matrix[row][col])

        return path


# --- Test it ---
s = Solution()

m1 = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print("Example 1:", s.column_major_traversal(m1))   # [1, 4, 7, 2, 5, 8, 3, 6, 9]

m2 = [[3, 2, 1, 7], [0, 6, 3, 2]]
print("Example 2:", s.column_major_traversal(m2))   # [3, 0, 2, 6, 1, 3, 7, 2]

m3 = [[1]]
print("Example 3:", s.column_major_traversal(m3))   # [1]

m4 = []
print("Empty:    ", s.column_major_traversal(m4))   # []

Step	`col`	`row`	Element appended	`path` so far
1	0	0	3	`[3]`
2	0	1	0	`[3, 0]`
3	1	0	2	`[3, 0, 2]`
4	1	1	6	`[3, 0, 2, 6]`
5	2	0	1	`[3, 0, 2, 6, 1]`
6	2	1	3	`[3, 0, 2, 6, 1, 3]`
7	3	0	7	`[3, 0, 2, 6, 1, 3, 7]`
8	3	1	2	`[3, 0, 2, 6, 1, 3, 7, 2]`

Row-Major vs Column-Major — The Full Comparison

# Side-by-side comparison on the same matrix
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

rows = len(matrix)
cols = len(matrix[0])

row_major = [matrix[r][c] for r in range(rows) for c in range(cols)]
col_major = [matrix[r][c] for c in range(cols) for r in range(rows)]

print("Row-major:    ", row_major)   # [1, 2, 3, 4, 5, 6, 7, 8, 9]
print("Column-major: ", col_major)   # [1, 4, 7, 2, 5, 8, 3, 6, 9]

# The ONLY difference: which loop variable is outer vs inner

The entire difference is one loop swap. That’s all that separates row-major from column-major traversal in code.

Complexity Analysis

Time complexity: O(m × n)

Every element is visited exactly once — identical to row-major traversal.

Space complexity: O(m × n)

The output list holds all elements. If you’re processing without storing, it’s O(1) extra space.

Cache note: In Python and other row-major languages, column-major traversal accesses memory with a stride of num_cols between consecutive visits. Each step jumps num_cols elements forward in memory instead of 1. For large matrices this causes frequent cache misses and is measurably slower than row-major traversal — even though both are O(m × n).

Edge Cases

Scenario	Input	Output	Note
Empty matrix	`[]`	`[]`	Guard clause returns immediately
Single element	`[[5]]`	`[5]`	One col, one row — one iteration
Single row	`[[1, 2, 3, 4]]`	`[1, 2, 3, 4]`	Outer runs 4 times, inner runs once — same result as row-major here
Single column	`[[1], [2], [3]]`	`[1, 2, 3]`	Outer runs once, inner runs 3 times

Column-major traversal is row-major traversal with the two loop variables swapped: col goes outer (slow), row goes inner (fast). The algorithm, complexity, and guard clauses are identical — only the access order changes. And in a row-major language like Python, that one swap is enough to turn every access into a cache miss on large matrices.

Note Book