Row Major Traversal

The Problem

Given a 2D matrix, collect all of its elements in row-major order — left to right across each row, one row at a time — and return them as a flat list.

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

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

This is the direct application of everything learned in the previous two lessons. If you’ve understood row-major memory layout, the traversal code writes itself.

Examples

Example 1 — 3×3 matrix

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

Example 2 — 2×4 matrix

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

Example 3 — 1×1 matrix (edge case)

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

Intuition

Row-major traversal is exactly the path your eye naturally takes when reading a grid — left to right along the first row, then drop down and repeat for the next row, and so on.

More importantly, this is the same order elements are stored in memory for row-major languages. Traversing in this order means every access hits the next slot in memory — no jumping, no cache misses. It’s the fastest possible way to touch every element.

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart LR
  subgraph R0["Row 0"]
    n1["1"] --> n2["2"] --> n3["3"]
  end
  subgraph R1["Row 1"]
    n4["4"] --> n5["5"] --> n6["6"]
  end
  subgraph R2["Row 2"]
    n7["7"] --> n8["8"] --> n9["9"]
  end
  n3 -->|"next row ↓"| n4
  n6 -->|"next row ↓"| n7

Row-major traversal of a 3×3 matrix — finish each row completely before dropping to the next.

The collected output is a flat 1D list of all elements in visit order:

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

Output — all 9 elements in row-major order, as a flat list.

The Approach

The key observation is simple:

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

That’s it. The outer loop picks a row, the inner loop walks across every column in that row. Append each element as you go.

---
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 = []"]
  RowLoop["for row in 0 → m-1"]
  ColLoop["for col in 0 → n-1"]
  Append["path.append(matrix[row][col])"]
  Done(["return path"])

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

Algorithm flow — the inner loop exhausts all columns before the outer loop advances to the next row.

Solution

from typing import List

class Solution:
    def row_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 row (slow dimension)
        for row in range(rows):
            # Inner loop: one step per column (fast dimension)
            for col in range(cols):
                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.row_major_traversal(m1))   # [1, 2, 3, 4, 5, 6, 7, 8, 9]

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

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

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

Dry Run — Example 2

Let’s trace through [[3, 2, 1, 7], [0, 6, 3, 2]] step by step.

rows = 2, cols = 4, path = []

Return: [3, 2, 1, 7, 0, 6, 3, 2] ✓

Complexity Analysis

Time complexity: O(m × n)

Every element in the matrix is visited exactly once. With m rows and n columns, that’s m × n total steps — no wasted work.

Space complexity: O(m × n)

The output list path holds every element — it’s the same size as the input. If you’re only asked to process elements without storing them, space drops to O(1) (just the two loop counters).

Cache bonus: Because row-major traversal accesses elements in the exact order they’re stored in memory, every access is a cache hit. In practice this means large matrices traverse significantly faster than the equivalent column-major loop, even though the big-O complexity is identical.

Edge Cases

Key Takeaway

Row-major traversal is two nested loops — outer over rows, inner over columns. It’s cache-optimal, it matches memory layout, and it’s the pattern the hardware was designed to reward. Whenever you traverse a 2D array in a row-major language, this is the loop order you want.