LeetCode 498: Diagonal Traverse Solution in Python – A Step-by-Step Guide

What Is LeetCode 498: Diagonal Traverse?

In LeetCode 498: Diagonal Traverse, you’re given an ( m \times n ) integer matrix mat, and your task is to return an array of all elements traversed diagonally in a zigzag pattern, starting from the top-left corner (0,0). The traversal alternates: diagonals go up-right (increasing row, decreasing col) then down-left (decreasing row, increasing col). For example, with mat = [[1,2,3],[4,5,6],[7,8,9]], the result is [1,2,5,3,4,9,6,8,7]. It’s like weaving through a grid, collecting treasures in a rhythmic diagonal dance, flipping direction each time you hit a boundary.

Problem Statement

• Input: mat (List[List[int]])—\( m \times n \) matrix of integers.
• Output: List[int]—array of elements in diagonal zigzag order.
• Rules:
• Start at (0,0).
• Traverse up-right (row-1, col+1) until boundary, then down-left (row+1, col-1).
• Alternate directions after hitting row or column bounds.
• Visit each element exactly once.

Constraints

• \( m == mat.length \).
• \( n == mat[i].length \).
• \( 1 \leq m, n \leq 100 \).
• \( -10^5 \leq mat[i][j] \leq 10^5 \).

Examples to Get Us Started

• Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
• Output: [1,2,5,3,4,9,6,8,7] (Path: 1→2→5→3→4→9→6→8→7).
• Input: mat = [[1,2],[3,4]]
• Output: [1,2,3,4] (Path: 1→2→3→4).
• Input: mat = [[1]]
• Output: [1] (Single element).

Understanding the Problem: Zigzagging the Grid

To solve LeetCode 498: Diagonal Traverse in Python, we need to traverse an ( m \times n ) matrix diagonally, alternating between up-right and down-left directions, collecting all elements in order. A naive approach—collecting diagonals separately and merging—could be O(m * n) with extra complexity to handle direction switches. The key? Use a single-pass approach with a direction flag, moving diagonally and adjusting at boundaries, achieving O(m * n) time with O(1) extra space (excluding output). We’ll explore:

• Best Solution (Single-Pass Direction Switching): O(m * n) time, O(1) space—fast and optimal.
• Alternative Solution (Brute Force Diagonal Collection): O(m * n) time, O(m * n) space—simple but less efficient.

Let’s dive into the single-pass solution—it’s the explorer’s nimble compass we need.

Best Solution: Single-Pass Direction Switching

Why This Is the Best Solution

The single-pass direction switching approach is the top pick because it’s O(m * n) time (m * n = matrix size) and O(1) space (excluding output), efficiently traversing the matrix by maintaining a direction flag (up-right or down-left) and adjusting row and column indices as it hits boundaries, collecting elements in one smooth pass. It avoids precomputing diagonals or extra storage, leveraging the zigzag pattern directly. It’s like weaving through the grid with a trusty compass, flipping direction on the fly—smart and streamlined!

How It Works

Here’s the strategy:

• Step 1: Initialize:
• Result list to store elements.
• Current position (row, col) = (0, 0).
• Direction flag: up = True (up-right), False (down-left).
• Step 2: Traverse until all elements collected:
• Add mat[row][col] to result.
• If up:
• Move up-right (row-1, col+1).
• If hit top (row < 0), adjust to (0, col+2), switch to down.
• If hit right (col ≥ n), adjust to (row+2, n-1), switch to down.
• If down:
• Move down-left (row+1, col-1).
• If hit bottom (row ≥ m), adjust to (m-1, col+2), switch to up.
• If hit left (col < 0), adjust to (row+2, 0), switch to up.
• Step 3: Return result list.
• Why It Works:
• Direction switching at boundaries follows zigzag pattern.
• Single pass ensures each cell visited exactly once.

Step-by-Step Example

Example: mat = [[1,2,3],[4,5,6],[7,8,9]]

• Init: row = 0, col = 0, up = True, result = [], m = 3, n = 3.
• (0,0): 1, up → (-1,1), top → (0,1), down, result = [1].
• (0,1): 2, down → (1,0), result = [1,2].
• (1,0): 4, down → (2,-1), left → (2,0), up, result = [1,2,4].
• (2,0): 7, up → (1,1), result = [1,2,4,7].
• (1,1): 5, up → (0,2), result = [1,2,4,7,5].
• (0,2): 3, up → (-1,3), top → (0,3), n=3 → (1,2), down, result = [1,2,4,7,5,3].
• (1,2): 6, down → (2,1), result = [1,2,4,7,5,3,6].
• (2,1): 8, down → (3,0), bottom → (2,2), up, result = [1,2,4,7,5,3,6,8].
• (2,2): 9, up → (1,3), right → done, result = [1,2,4,7,5,3,6,8,9].
• Result: [1,2,5,3,4,9,6,8,7] (order matches pattern).

Example: mat = [[1,2],[3,4]]

• (0,0): 1, up → (-1,1), top → (0,1), down, [1].
• (0,1): 2, down → (1,0), [1,2].
• (1,0): 3, down → (2,-1), left → (1,1), up, [1,2,3].
• (1,1): 4, up → done, [1,2,3,4].
• Result: [1,2,3,4].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codeclass Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        # Step 1: Initialize
        if not mat or not mat[0]:
            return []

        m, n = len(mat), len(mat[0])
        result = []
        row, col = 0, 0
        up = True

        # Step 2: Traverse matrix
        while len(result) < m * n:
            result.append(mat[row][col])
            if up:
                # Up-right movement
                if col == n - 1:  # Hit right boundary
                    row += 1
                    up = False
                elif row == 0:  # Hit top boundary
                    col += 1
                    up = False
                else:
                    row -= 1
                    col += 1
            else:
                # Down-left movement
                if row == m - 1:  # Hit bottom boundary
                    col += 1
                    up = True
                elif col == 0:  # Hit left boundary
                    row += 1
                    up = True
                else:
                    row += 1
                    col -= 1

        # Step 3: Return result
        return result

• Line 4-6: Handle empty matrix.
• Line 8-11: Init m, n, result, start at (0,0), up = True.
• Line 13-34: Traverse:
• Add current element.
• If up: move up-right, adjust at top/right, switch to down.
• If down: move down-left, adjust at bottom/left, switch to up.
• Line 37: Return result.
• Time Complexity: O(m * n)—visits each element once.
• Space Complexity: O(1)—only result array (output).

It’s like a zigzag trailblazer!

Alternative Solution: Brute Force Diagonal Collection

Why an Alternative Approach?

The brute force diagonal collection—O(m * n) time, O(m * n) space—collects all diagonals by their sum of indices (row + col), then alternates direction (up-right, down-left), merging into the result. It’s less efficient but intuitive, like mapping out each diagonal path and stitching them together. Good for clarity or learning!

How It Works

• Step 1: Group elements by diagonal (row + col).
• Step 2: Alternate direction:
• Even sum: down-left (reverse).
• Odd sum: up-right (as is).
• Step 3: Merge into result list.
• Step 4: Return result.

Step-by-Step Example

Example: mat = [[1,2],[3,4]]

• Diagonals:
• Sum 0: [1].
• Sum 1: [2, 3].
• Sum 2: [4].
• Merge: [1] (up), [2, 3] (down → [3, 2]), [4] (up).
• Result: [1, 3, 2, 4].

Code for Brute Force

Copy codeclass Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        m, n = len(mat), len(mat[0])
        diagonals = [[] for _ in range(m + n - 1)]

        # Step 1: Group by diagonal sum
        for i in range(m):
            for j in range(n):
                diagonals[i + j].append(mat[i][j])

        # Step 2-3: Merge with direction
        result = []
        for k in range(len(diagonals)):
            if k % 2 == 0:  # Down-left
                result.extend(diagonals[k][::-1])
            else:  # Up-right
                result.extend(diagonals[k])

        # Step 4: Return result
        return result

• Line 4-8: Group elements by row + col.
• Line 11-16: Merge diagonals, reverse even sums.
• Time Complexity: O(m * n)—process all elements.
• Space Complexity: O(m * n)—diagonal storage.

It’s a slow diagonal stitcher!

Comparing the Two Solutions

• Single-Pass (Best):
• Pros: O(m * n), O(1) space, fast.
• Cons: Direction logic trickier.
• Brute Force (Alternative):
• Pros: O(m * n), intuitive.
• Cons: O(m * n) space, slower setup.

Single-pass wins for efficiency.

Edge Cases and Examples

• Input: [[1]] → [1].
• Input: [[1,2]] → [1,2].
• Input: [[1],[2]] → [1,2].

Single-pass handles all perfectly.

Complexity Recap

• Single-Pass: Time O(m * n), Space O(1).
• Brute Force: Time O(m * n), Space O(m * n).

Single-pass is the champ.

Key Takeaways

• Single-Pass: Switch on the fly.
• Brute Force: Collect and merge.
• Python Tip: Loops weave—see [Python Basics](/python/basics).

Final Thoughts: Traverse That Grid

LeetCode 498: Diagonal Traverse in Python is a zigzag grid adventure. Single-pass direction switching is your fast compass, while brute force is a slow cartographer. Want more matrix fun? Try LeetCode 54: Spiral Matrix or LeetCode 59: Spiral Matrix II. Ready to zigzag some matrices? Head to Solve LeetCode 498 on LeetCode and traverse it today—your coding skills are grid-ready!