Matrix Data Structure

def solve_matrix_problem(matrix):
    if not matrix or not matrix[0]:
        return default_result
    
    rows, cols = len(matrix), len(matrix[0])
    
    # Initialize result structure
    result = initialize_result(rows, cols)
    
    # Main processing loop
    for i in range(rows):
        for j in range(cols):
            # Process current cell
            process_cell(matrix, i, j, result)
    
    return result

def process_cell(matrix, row, col, result):
    # Template for cell processing
    # - Check boundaries
    # - Apply logic
    # - Update result
    pass

def spiral_traversal(matrix):
    if not matrix or not matrix[0]:
        return []
    
    result = []
    rows, cols = len(matrix), len(matrix[0])
    
    # Define boundaries
    top, bottom = 0, rows - 1
    left, right = 0, cols - 1
    
    while top <= bottom and left <= right:
        # Right movement
        for j in range(left, right + 1):
            result.append(matrix[top][j])
        top += 1
        
        # Down movement  
        for i in range(top, bottom + 1):
            result.append(matrix[i][right])
        right -= 1
        
        # Left movement (if still valid row)
        if top <= bottom:
            for j in range(right, left - 1, -1):
                result.append(matrix[bottom][j])
            bottom -= 1
        
        # Up movement (if still valid column)
        if left <= right:
            for i in range(bottom, top - 1, -1):
                result.append(matrix[i][left])
            left += 1
    
    return result

def rotate_matrix_90_clockwise(matrix):
    """
    Two-step approach: Transpose + Reverse rows
    """
    n = len(matrix)
    
    # Step 1: Transpose matrix (swap matrix[i][j] with matrix[j][i])
    for i in range(n):
        for j in range(i + 1, n):  # Start from i+1 to avoid double swap
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    
    # Step 2: Reverse each row
    for i in range(n):
        matrix[i].reverse()
    
    return matrix

def transpose_matrix(matrix):
    """
    Create new matrix with swapped dimensions
    """
    if not matrix or not matrix[0]:
        return []
    
    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]
    
    return result

def search_matrix_binary(matrix, target):
    """
    Binary search on sorted matrix (treat as 1D array)
    """
    if not matrix or not matrix[0]:
        return False
    
    rows, cols = len(matrix), len(matrix[0])
    left, right = 0, rows * cols - 1
    
    while left <= right:
        mid = (left + right) // 2
        mid_row, mid_col = mid // cols, mid % cols
        mid_val = matrix[mid_row][mid_col]
        
        if mid_val == target:
            return True
        elif mid_val < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return False

def search_matrix_elimination(matrix, target):
    """
    Search in row-wise and column-wise sorted matrix
    Start from top-right or bottom-left corner
    """
    if not matrix or not matrix[0]:
        return False
    
    rows, cols = len(matrix), len(matrix[0])
    row, col = 0, cols - 1  # Start from top-right
    
    while row < rows and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] > target:
            col -= 1  # Move left
        else:
            row += 1  # Move down
    
    return False

def set_matrix_zeros(matrix):
    """
    Set entire row and column to zero if any element is zero
    """
    if not matrix or not matrix[0]:
        return
    
    rows, cols = len(matrix), len(matrix[0])
    
    # Use first row and column as markers
    first_row_zero = any(matrix[0][j] == 0 for j in range(cols))
    first_col_zero = any(matrix[i][0] == 0 for i in range(rows))
    
    # Mark zeros in first row and column
    for i in range(1, rows):
        for j in range(1, cols):
            if matrix[i][j] == 0:
                matrix[0][j] = 0  # Mark column
                matrix[i][0] = 0  # Mark row
    
    # Set zeros based on markers
    for i in range(1, rows):
        for j in range(1, cols):
            if matrix[0][j] == 0 or matrix[i][0] == 0:
                matrix[i][j] = 0
    
    # Handle first row and column
    if first_row_zero:
        for j in range(cols):
            matrix[0][j] = 0
    if first_col_zero:
        for i in range(rows):
            matrix[i][0] = 0

def multiply_matrices(A, B):
    """
    Standard matrix multiplication: C[i][j] = sum(A[i][k] * B[k][j])
    """
    if not A or not A[0] or not B or not B[0]:
        return []
    
    rows_A, cols_A = len(A), len(A[0])
    rows_B, cols_B = len(B), len(B[0])
    
    if cols_A != rows_B:
        return []  # Invalid dimensions
    
    result = [[0] * cols_B for _ in range(rows_A)]
    
    for i in range(rows_A):
        for j in range(cols_B):
            for k in range(cols_A):
                result[i][j] += A[i][k] * B[k][j]
    
    return result

def multiply_sparse_matrices(A, B):
    """
    Optimized multiplication for sparse matrices
    """
    if not A or not A[0] or not B or not B[0]:
        return []
    
    rows_A, cols_A = len(A), len(A[0])
    rows_B, cols_B = len(B), len(B[0])
    result = [[0] * cols_B for _ in range(rows_A)]
    
    for i in range(rows_A):
        for k in range(cols_A):
            if A[i][k] != 0:  # Skip if zero
                for j in range(cols_B):
                    result[i][j] += A[i][k] * B[k][j]
    
    return result

def build_prefix_sum_2d(mat):
    """
    Build 2D prefix sum matrix for O(1) range sum queries.

    Key Formula:
    - Build: pref[i+1][j+1] = mat[i][j] + pref[i][j+1] + pref[i+1][j] - pref[i][j]
    - Query: sum(r1,c1 to r2,c2) = pref[r2+1][c2+1] - pref[r1][c2+1] - pref[r2+1][c1] + pref[r1][c1]

    Time: O(m*n) build, O(1) query
    Space: O(m*n)
    """
    if not mat or not mat[0]:
        return []

    m, n = len(mat), len(mat[0])

    # Size (m+1) x (n+1) for easier boundary handling (row 0 and col 0 are zeros)
    pref = [[0] * (n + 1) for _ in range(m + 1)]

    # Build prefix sum
    for i in range(m):
        for j in range(n):
            pref[i + 1][j + 1] = mat[i][j] + pref[i][j + 1] + pref[i + 1][j] - pref[i][j]

    return pref

def range_sum_2d(pref, r1, c1, r2, c2):
    """
    Get sum of rectangle from (r1,c1) to (r2,c2) inclusive.

    Visual explanation:
    ┌───────────────────┐
    │   A    │    B     │
    │────────┼──────────│ ← r1
    │   C    │ TARGET   │
    │────────┼──────────│ ← r2
    └───────────────────┘
              c1       c2

    TARGET = Total - A - C + TopLeft (since TopLeft subtracted twice)
           = pref[r2+1][c2+1] - pref[r1][c2+1] - pref[r2+1][c1] + pref[r1][c1]
    """
    return pref[r2 + 1][c2 + 1] - pref[r1][c2 + 1] - pref[r2 + 1][c1] + pref[r1][c1]


def matrix_block_sum(mat, k):
    """
    LC 1314: For each cell, return sum of all elements within k distance.
    """
    m, n = len(mat), len(mat[0])
    pref = build_prefix_sum_2d(mat)
    res = [[0] * n for _ in range(m)]

    for i in range(m):
        for j in range(n):
            # Clamp boundaries
            r1 = max(0, i - k)
            c1 = max(0, j - k)
            r2 = min(m - 1, i + k)
            c2 = min(n - 1, j + k)

            res[i][j] = range_sum_2d(pref, r1, c1, r2, c2)

    return res

def min_path_sum(grid):
    """
    Find minimum path sum from top-left to bottom-right
    """
    if not grid or not grid[0]:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    
    # Initialize DP table (can modify grid in-place to save space)
    dp = [[0] * cols for _ in range(rows)]
    dp[0][0] = grid[0][0]
    
    # Fill first row
    for j in range(1, cols):
        dp[0][j] = dp[0][j-1] + grid[0][j]
    
    # Fill first column
    for i in range(1, rows):
        dp[i][0] = dp[i-1][0] + grid[i][0]
    
    # Fill rest of the table
    for i in range(1, rows):
        for j in range(1, cols):
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
    
    return dp[rows-1][cols-1]

def unique_paths(m, n):
    """
    Count unique paths from top-left to bottom-right
    """
    dp = [[1] * n for _ in range(m)]
    
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    
    return dp[m-1][n-1]

Example (3×4 matrix) — diagonal keys (i - j):
       j=0   j=1   j=2   j=3
i=0  [  0 ] [ -1 ] [ -2 ] [ -3 ]
i=1  [  1 ] [  0 ] [ -1 ] [ -2 ]
i=2  [  2 ] [  1 ] [  0 ] [ -1 ]

Diagonal key 0  → (0,0), (1,1), (2,2)       ← main diagonal
Diagonal key -1 → (0,1), (1,2), (2,3)       ← above main
Diagonal key  1 → (1,0), (2,1)              ← below main

// Step 1: group elements by diagonal key
Map<Integer, PriorityQueue<Integer>> map = new HashMap<>();
for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
        map.computeIfAbsent(i - j, k -> new PriorityQueue<>()).add(mat[i][j]);

// Step 2: refill matrix — traverse in same row-major order
for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
        mat[i][j] = map.get(i - j).poll();   // min-heap gives ascending order

Primary Diagonal (i, i):           Secondary Diagonal (i, n-1-i):

      Col 0   Col 1   Col 2   Col 3        Col 0   Col 1   Col 2   Col 3
Row 0 [ X ]   [ . ]   [ . ]   [ . ]  Row 0 [ . ]   [ . ]   [ . ]   [ X ]  ← (0, 3)
Row 1 [ . ]   [ X ]   [ . ]   [ . ]  Row 1 [ . ]   [ . ]   [ X ]   [ . ]  ← (1, 2)
Row 2 [ . ]   [ . ]   [ X ]   [ . ]  Row 2 [ . ]   [ X ]   [ . ]   [ . ]  ← (2, 1)
Row 3 [ . ]   [ . ]   [ . ]   [ X ]  Row 3 [ X ]   [ . ]   [ . ]   [ . ]  ← (3, 0)
        ↓       ↓       ↓       ↓
      (0,0)   (1,1)   (2,2)   (3,3)

Both Diagonals Together:
      Col 0   Col 1   Col 2   Col 3
Row 0 [ P ]   [ . ]   [ . ]   [ S ]    P = Primary, S = Secondary
Row 1 [ . ]   [ P ]   [ S ]   [ . ]
Row 2 [ . ]   [ S ]   [ P ]   [ . ]
Row 3 [ S ]   [ . ]   [ . ]   [ P ]

3×3 Matrix (n=3):
      Col 0   Col 1   Col 2
Row 0 [ P ]   [ . ]   [ S ]    (0,0) and (0,2)
Row 1 [ . ]   [P&S]   [ . ]    (1,1) is BOTH primary AND secondary!
Row 2 [ S ]   [ . ]   [ P ]    (2,0) and (2,2)

Center cell (1,1): i=1, i=1 (primary) AND n-1-i=3-1-1=1 (secondary)

def get_diagonal_elements(matrix):
    """
    Get all elements on both diagonals of a square matrix.
    """
    if not matrix or not matrix[0]:
        return []

    n = len(matrix)
    elements = set()  # Use set to avoid double-counting center in odd-sized matrix

    for i in range(n):
        # Primary diagonal: (i, i)
        elements.add(matrix[i][i])

        # Secondary diagonal: (i, n - 1 - i)
        elements.add(matrix[i][n - 1 - i])

    return list(elements)

def process_diagonals(matrix):
    """
    Process both diagonals with explicit handling of intersection.
    """
    n = len(matrix)
    result = 0

    for i in range(n):
        # Process primary diagonal
        result = process(matrix[i][i], result)

        # Process secondary diagonal (skip if same as primary to avoid double-processing)
        if i != n - 1 - i:  # Not the center cell
            result = process(matrix[i][n - 1 - i], result)

    return result

// From LC 2614 - Prime In Diagonal
public int diagonalPrime(int[][] nums) {
    int n = nums.length;
    int maxPrime = 0;

    for (int i = 0; i < n; i++) {
        // 1. Primary Diagonal: (i, i)
        int val1 = nums[i][i];
        if (val1 > maxPrime && isPrime(val1)) {
            maxPrime = val1;
        }

        // 2. Secondary Diagonal: (i, n - 1 - i)
        int val2 = nums[i][n - 1 - i];
        if (val2 > maxPrime && isPrime(val2)) {
            maxPrime = val2;
        }
    }
    return maxPrime;
}

# Standard matrix indexing: matrix[row][col]
# For matrix[i][j]:
# - i represents row (vertical position)
# - j represents column (horizontal position)

# Direction vectors for 4-directional movement
directions = [(0,1), (1,0), (0,-1), (-1,0)]  # right, down, left, up

# Direction vectors for 8-directional movement  
directions_8 = [(0,1), (1,0), (0,-1), (-1,0), (1,1), (1,-1), (-1,1), (-1,-1)]

# Boundary checking
def is_valid(row, col, rows, cols):
    return 0 <= row < rows and 0 <= col < cols

Matrix Problem Analysis Flowchart:

1. Is the problem about traversing matrix in a specific order?
   ├── YES → Use Matrix Traversal Template
   │   ├── Spiral order? → Boundary tracking approach
   │   ├── Diagonal order? → Direction alternation approach
   │   └── Custom order? → Direction vectors approach
   └── NO → Continue to 2

2. Does the problem require matrix transformation (rotate, flip, transpose)?
   ├── YES → Use Matrix Transformation Template
   │   ├── Rotate 90°? → Transpose + reverse rows
   │   ├── General rotation? → Mathematical coordinate mapping
   │   └── Transpose? → Swap (i,j) with (j,i)
   └── NO → Continue to 3

3. Is it a search problem in a sorted/partially sorted matrix?
   ├── YES → Use Matrix Search Template
   │   ├── Fully sorted (row-wise + col-wise)? → Binary search as 1D array
   │   ├── Row-wise and column-wise sorted? → Elimination approach
   │   └── Partially sorted? → Modified binary search
   └── NO → Continue to 4

4. Does the problem modify matrix elements based on conditions?
   ├── YES → Use Matrix Modification Template
   │   ├── Set zeros? → Use first row/column as markers
   │   ├── Smooth/average? → 8-directional neighbor processing
   │   └── State transitions? → Two-pass or auxiliary space
   └── NO → Continue to 5

5. Is it a mathematical operation between matrices?
   ├── YES → Use Matrix Multiplication Template
   │   ├── Standard multiplication? → Triple nested loop
   │   ├── Sparse matrices? → Skip-zero optimization
   │   └── Special operations? → Customize based on operation
   └── NO → Continue to 6

6. Is it about finding paths or optimizing values through the matrix?
   ├── YES → Use Matrix Path DP Template
   │   ├── Count paths? → DP with path counting
   │   ├── Min/Max path cost? → DP with optimization
   │   └── Complex constraints? → DFS + memoization
   └── NO → Use Universal Matrix Template

top, bottom = 0, rows - 1
left, right = 0, cols - 1
while top <= bottom and left <= right:
    ...        # process boundaries, then move them inward

# 4-directional movement
directions = [(0,1), (1,0), (0,-1), (-1,0)]
# 8-directional movement  
directions = [(di,dj) for di in [-1,0,1] for dj in [-1,0,1]]

# Use first row/column as markers
first_row_zero = any(matrix[0][j] == 0 for j in range(cols))
first_col_zero = any(matrix[i][0] == 0 for i in range(rows))

# 90° clockwise rotation: (i,j) → (j, n-1-i)
# Transpose: (i,j) → (j,i)
# Flip horizontal: (i,j) → (i, n-1-j)

# Matrix[row][col] → index = row * cols + col
# Index → row = index // cols, col = index % cols