please iudjerstand the approach the format and the structure and this is for matrixes in the same  wau genreate for all patterns like like all dont leave anyhthong dont ignore anything for graph 
"""
Comprehensive Guide to Matrix Problems in Data Structures and Algorithms (DSA)
Welcome to this Comprehensive Guide to Matrix Problems in Data Structures and Algorithms (DSA). Matrices are fundamental data structures that form the backbone of numerous computational problems, from basic traversals to complex dynamic programming challenges. This guide is meticulously crafted to cover all major matrix-related problem patterns, ranging from easy to medium difficulty. Each pattern is illustrated with example problems, step-by-step solutions, and clear explanations to ensure a thorough understanding.
Table of Contents
Introduction to Matrices
Pattern 1: Matrix Traversal
Row-wise and Column-wise Traversal
Spiral Order Traversal
Diagonal Traversal
Boundary Traversal
Pattern 2: Searching in a Matrix
Search in a Row-wise and Column-wise Sorted Matrix
Search in a Binary Matrix
Pattern 3: Matrix Manipulation
Transpose of a Matrix
Rotate Matrix by 90 Degrees Clockwise
Rotate Matrix by 90 Degrees Anti-Clockwise
Set Matrix Zeroes
Flip Matrix Horizontally and Vertically
Pattern 4: Dynamic Programming on Matrices
Maximum Path Sum in a Matrix
Unique Paths in a Grid
Longest Increasing Path in a Matrix
Pattern 5: Matrix-Based Pattern Problems
Print a Binary Matrix Pattern ("X" Pattern)
Print a Hollow Rectangle Pattern
Print a Butterfly Pattern
Pattern 6: Graph-Like Problems Using Matrices
Number of Islands
Word Search in a Grid
Pattern 7: Matrix Operations
Matrix Addition
Matrix Multiplication
Matrix Exponentiation
Pattern 8: Advanced Traversal Techniques
Depth-First Search (DFS) in a Matrix
Breadth-First Search (BFS) in a Matrix
Conclusion

Introduction to Matrices
A matrix is a two-dimensional array of elements arranged in rows and columns. In DSA, matrices are used to represent various structures such as grids, graphs, and tables. Mastery of matrix manipulation and traversal is essential for solving a wide range of algorithmic challenges.
Key Concepts
Dimensions: A matrix with m rows and n columns is termed an m x n matrix.
Accessing Elements: Elements are accessed using their row and column indices, typically starting from 0 or 1.
Common Operations: Traversal, searching, insertion, deletion, updating elements, transposition, rotation, etc.
Representation
Matrices can be represented in programming languages as lists of lists (in Python), 2D arrays (in C/C++/Java), or other similar data structures.
Example (Python):
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]


Pattern 1: Matrix Traversal
Matrix traversal involves visiting each element systematically. Different traversal orders are employed based on problem requirements.
1.1 Row-wise and Column-wise Traversal
Problem Statement:
Given a matrix of size m x n, print all its elements first row-wise and then column-wise.
Example:
Input:
Matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]

Output:
Row-wise traversal: 1 2 3 4 5 6 7 8 9
Column-wise traversal: 1 4 7 2 5 8 3 6 9

Solution:
Row-wise Traversal: Iterate through each row and within each row, iterate through each column.
Column-wise Traversal: Iterate through each column first and then iterate through each row within that column.
Implementation (Python):
def traverse_matrix(matrix):
    m = len(matrix)
    n = len(matrix[0]) if m > 0 else 0

    # Row-wise traversal
    print("Row-wise traversal:", end=" ")
    for i in range(m):
        for j in range(n):
            print(matrix[i][j], end=" ")
    print()

    # Column-wise traversal
    print("Column-wise traversal:", end=" ")
    for j in range(n):
        for i in range(m):
            print(matrix[i][j], end=" ")
    print()

# Example usage
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
traverse_matrix(matrix)

Output:
Row-wise traversal: 1 2 3 4 5 6 7 8 9 
Column-wise traversal: 1 4 7 2 5 8 3 6 9 

1.2 Spiral Order Traversal
Problem Statement:
Given a matrix, print the elements in spiral order starting from the top-left corner.
Example:
Input:
Matrix = [
  [1,  2,  3, 4],
  [5,  6,  7, 8],
  [9, 10, 11,12],
  [13,14, 15,16]
]

Output:
Spiral Order: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

Solution:
Spiral traversal involves iteratively traversing the outer layers of the matrix and moving towards the inner layers using four pointers: top, bottom, left, and right.
Step-by-Step:
Initialize four pointers:
top = 0
bottom = m - 1
left = 0
right = n - 1
While top <= bottom and left <= right, perform the following:
Traverse from left to right along the top row.
Increment top.
Traverse from top to bottom along the right column.
Decrement right.
If top <= bottom, traverse from right to left along the bottom row.
Decrement bottom.
If left <= right, traverse from bottom to top along the left column.
Increment left.
Implementation (Python):
def spiral_order(matrix):
    if not matrix:
        return []

    spiral = []
    m, n = len(matrix), len(matrix[0])
    top, bottom = 0, m - 1
    left, right = 0, n - 1

    while top <= bottom and left <= right:
        # Traverse Top Row
        for j in range(left, right + 1):
            spiral.append(matrix[top][j])
        top += 1

        # Traverse Right Column
        for i in range(top, bottom + 1):
            spiral.append(matrix[i][right])
        right -= 1

        # Traverse Bottom Row
        if top <= bottom:
            for j in range(right, left - 1, -1):
                spiral.append(matrix[bottom][j])
            bottom -= 1

        # Traverse Left Column
        if left <= right:
            for i in range(bottom, top - 1, -1):
                spiral.append(matrix[i][left])
            left += 1

    return spiral

# Example usage
matrix = [
    [1,  2,  3, 4],
    [5,  6,  7, 8],
    [9, 10, 11,12],
    [13,14, 15,16]
]
print("Spiral Order:", ' '.join(map(str, spiral_order(matrix))))

Output:
Spiral Order: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

1.3 Diagonal Traversal
Problem Statement:
Given a matrix, print all elements of the matrix in diagonal order starting from the top-left element.
Example:
Input:
Matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]

Output:
Diagonal Order: 1 2 4 7 5 3 6 8 9

Solution:
Diagonal traversal can be done by iterating through all possible diagonals where the sum of indices (i + j) is constant for each diagonal. Depending on the direction (up or down), traverse accordingly.
Implementation (Python):
def diagonal_order(matrix):
    if not matrix:
        return []

    m, n = len(matrix), len(matrix[0])
    result = []
    for d in range(m + n -1):
        if d % 2 == 0:
            # Even diagonal: traverse upwards
            i = min(d, m-1)
            j = d - i
            while i >=0 and j < n:
                result.append(matrix[i][j])
                i -=1
                j +=1
        else:
            # Odd diagonal: traverse downwards
            j = min(d, n-1)
            i = d - j
            while j >=0 and i < m:
                result.append(matrix[i][j])
                i +=1
                j -=1
    return result

# Example usage
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
print("Diagonal Order:", ' '.join(map(str, diagonal_order(matrix))))

Output:
Diagonal Order: 1 2 4 7 5 3 6 8 9

1.4 Boundary Traversal
Problem Statement:
Given a matrix, print all elements on the boundary of the matrix in clockwise order.
Example:
Input:
Matrix = [
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12],
  [13,14,15,16]
]

Output:
Boundary Traversal: 1 2 3 4 8 12 16 15 14 13 9 5

Solution:
Traverse the top row, rightmost column, bottom row, and leftmost column sequentially, ensuring no duplicates.
Implementation (Python):
def boundary_traversal(matrix):
    if not matrix:
        return []

    m, n = len(matrix), len(matrix[0])
    boundary = []

    # Top row
    for j in range(n):
        boundary.append(matrix[0][j])

    # Right column
    for i in range(1, m):
        boundary.append(matrix[i][n-1])

    # Bottom row
    if m > 1:
        for j in range(n-2, -1, -1):
            boundary.append(matrix[m-1][j])

    # Left column
    if n > 1:
        for i in range(m-2, 0, -1):
            boundary.append(matrix[i][0])

    return boundary

# Example usage
matrix = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9,10,11,12],
    [13,14,15,16]
]
print("Boundary Traversal:", ' '.join(map(str, boundary_traversal(matrix))))

Output:
Boundary Traversal: 1 2 3 4 8 12 16 15 14 13 9 5


Pattern 2: Searching in a Matrix
Efficient searching in a matrix is crucial, especially for large datasets or matrices with specific properties.
2.1 Search in a Row-wise and Column-wise Sorted Matrix
Problem Statement:
Given an m x n matrix where each row and each column is sorted in ascending order, write an efficient algorithm to search for a target value.
Example:
Input:
Matrix = [
  [10, 20, 30, 40],
  [15, 25, 35, 45],
  [27, 29, 37, 48],
  [32, 33, 39, 50]
]
Target = 29

Output:
Element found at position (2, 1)

Solution:
Start from the top-right corner. If the current element is greater than the target, move left; if less, move down.
Implementation (Python):
def search_sorted_matrix(matrix, target):
    if not matrix:
        return (-1, -1)

    m, n = len(matrix), len(matrix[0])
    i, j = 0, n - 1  # Start from top-right

    while i < m and j >= 0:
        current = matrix[i][j]
        if current == target:
            return (i, j)
        elif current > target:
            j -= 1  # Move left
        else:
            i += 1  # Move down

    return (-1, -1)  # Not found

# Example usage
matrix = [
    [10, 20, 30, 40],
    [15, 25, 35, 45],
    [27, 29, 37, 48],
    [32, 33, 39, 50]
]
target = 29
position = search_sorted_matrix(matrix, target)
if position != (-1, -1):
    print(f"Element found at position {position}")
else:
    print("Element not found")

Output:
Element found at position (2, 1)

2.2 Search in a Binary Matrix
Problem Statement:
Given a binary matrix where each row is sorted in non-decreasing order, write an efficient algorithm to count the number of 1s in the matrix.
Example:
Input:
Matrix = [
  [0, 0, 1, 1],
  [0, 1, 1, 1],
  [1, 1, 1, 1]
]

Output:
Number of 1's: 9

Solution:
Start from the top-right corner. Move left when you encounter a 1, and count them.
Implementation (Python):
def count_ones(matrix):
    if not matrix:
        return 0

    m, n = len(matrix), len(matrix[0])
    count = 0
    i, j = 0, n - 1  # Start from top-right

    while i < m and j >= 0:
        if matrix[i][j] == 1:
            count += (j + 1)  # All elements to the left are 1
            i += 1  # Move to next row
        else:
            j -= 1  # Move left

    return count

# Example usage
matrix = [
    [0, 0, 1, 1],
    [0, 1, 1, 1],
    [1, 1, 1, 1]
]
print("Number of 1's:", count_ones(matrix))

Output:
Number of 1's: 9


Pattern 3: Matrix Manipulation
Matrix manipulation includes operations such as transposing, rotating, flipping, and modifying elements based on conditions. These operations are fundamental in various algorithms and simulations.
3.1 Transpose of a Matrix
Problem Statement:
Given a matrix, compute its transpose without using additional space.
Example:
Input:
Matrix = [
  [1, 2, 3],
  [4, 5, 6]
]

Output:
Transposed Matrix = [
  [1, 4],
  [2, 5],
  [3, 6]
]

Solution:
The transpose of a matrix flips it over its diagonal, turning rows into columns and vice versa.
Implementation (Python):
def transpose_matrix(matrix):
    if not matrix:
        return []

    m, n = len(matrix), len(matrix[0])
    # Initialize transposed matrix
    transpose = [[0 for _ in range(m)] for _ in range(n)]

    for i in range(m):
        for j in range(n):
            transpose[j][i] = matrix[i][j]

    return transpose

# Example usage
matrix = [
    [1, 2, 3],
    [4, 5, 6]
]
transposed = transpose_matrix(matrix)
print("Transposed Matrix:")
for row in transposed:
    print(row)

Output:
Transposed Matrix:
[1, 4]
[2, 5]
[3, 6]

3.2 Rotate Matrix by 90 Degrees Clockwise
Problem Statement:
Rotate a given n x n matrix by 90 degrees clockwise in-place.
Example:
Input:
Matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]

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

Solution:
To rotate the matrix by 90 degrees clockwise:
Transpose the Matrix: Swap matrix[i][j] with matrix[j][i].
Reverse Each Row: Reverse the elements in each row.
Implementation (Python):
def rotate_matrix_90_clockwise(matrix):
    if not matrix:
        return []

    n = len(matrix)
    # Transpose the matrix
    for i in range(n):
        for j in range(i, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

    # Reverse each row
    for i in range(n):
        matrix[i].reverse()

    return matrix

# Example usage
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
rotated = rotate_matrix_90_clockwise(matrix)
print("Rotated Matrix:")
for row in rotated:
    print(row)

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

3.3 Rotate Matrix by 90 Degrees Anti-Clockwise
Problem Statement:
Rotate a given n x n matrix by 90 degrees anti-clockwise in-place.
Example:
Input:
Matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]

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

Solution:
To rotate the matrix by 90 degrees anti-clockwise:
Transpose the Matrix.
Reverse Each Column.
Implementation (Python):
def rotate_matrix_90_anticlockwise(matrix):
    if not matrix:
        return []

    n = len(matrix)
    # Transpose the matrix
    for i in range(n):
        for j in range(i, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

    # Reverse each column
    for j in range(n):
        for i in range(n // 2):
            matrix[i][j], matrix[n-1-i][j] = matrix[n-1-i][j], matrix[i][j]

    return matrix

# Example usage
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
rotated = rotate_matrix_90_anticlockwise(matrix)
print("Rotated Matrix:")
for row in rotated:
    print(row)

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

3.4 Set Matrix Zeroes
Problem Statement:
Given an m x n matrix, if an element is 0, set its entire row and column to 0. Perform this operation in-place.
Example:
Input:
Matrix = [
  [1, 1, 1],
  [1, 0, 1],
  [1, 1, 1]
]

Output:
Modified Matrix = [
  [1, 0, 1],
  [0, 0, 0],
  [1, 0, 1]
]

Solution:
Use the first row and first column to mark zeros for other rows and columns. Then iterate and set zeros accordingly, ensuring the first row and column are handled separately.
Implementation (Python):
def set_matrix_zeroes(matrix):
    if not matrix:
        return

    m, n = len(matrix), len(matrix[0])
    first_row_has_zero = any(matrix[0][j] == 0 for j in range(n))
    first_col_has_zero = any(matrix[i][0] == 0 for i in range(m))

    # Use first row and column as markers
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][j] == 0:
                matrix[i][0] = 0
                matrix[0][j] = 0

    # Set matrix elements to zero based on markers
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0

    # Set first row to zero if needed
    if first_row_has_zero:
        for j in range(n):
            matrix[0][j] = 0

    # Set first column to zero if needed
    if first_col_has_zero:
        for i in range(m):
            matrix[i][0] = 0

# Example usage
matrix = [
    [1, 1, 1],
    [1, 0, 1],
    [1, 1, 1]
]
set_matrix_zeroes(matrix)
print("Modified Matrix:")
for row in matrix:
    print(row)

Output:
Modified Matrix:
[1, 0, 1]
[0, 0, 0]
[1, 0, 1]

3.5 Flip Matrix Horizontally and Vertically
Problem Statement:
Given an m x n matrix, flip it horizontally (mirror along the vertical axis) and vertically (mirror along the horizontal axis).
Example:
Input:
Matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]

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

Vertically Flipped Matrix:
[7, 8, 9]
[4, 5, 6]
[1, 2, 3]

Solution:
Horizontal Flip: Reverse each row.
Vertical Flip: Reverse the order of rows.
Implementation (Python):
def flip_matrix_horizontally(matrix):
    for row in matrix:
        row.reverse()
    return matrix

def flip_matrix_vertically(matrix):
    matrix.reverse()
    return matrix

# Example usage
matrix_h = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
horizontally_flipped = flip_matrix_horizontally([row.copy() for row in matrix_h])
print("Horizontally Flipped Matrix:")
for row in horizontally_flipped:
    print(row)

matrix_v = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
vertically_flipped = flip_matrix_vertically([row.copy() for row in matrix_v])
print("\nVertically Flipped Matrix:")
for row in vertically_flipped:
    print(row)

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

Vertically Flipped Matrix:
[7, 8, 9]
[4, 5, 6]
[1, 2, 3]


Pattern 4: Dynamic Programming on Matrices
Dynamic Programming (DP) involves breaking down problems into overlapping subproblems and storing their solutions. When applied to matrices, DP can solve intricate problems like pathfinding, subset sums, and more.
4.1 Maximum Path Sum in a Matrix
Problem Statement:
Find the maximum sum path from the top-left corner to the bottom-right corner of a given m x n matrix. You can only move either down or right at any point in time.
Example:
Input:
Matrix = [
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1]
]

Output:
Maximum Path Sum: 12
Path: 1 → 3 → 5 → 2 → 1

Solution:
Use DP to compute the maximum sum to reach each cell by considering the maximum of the cell above and the cell to the left.
Implementation (Python):
def max_path_sum(matrix):
    if not matrix:
        return 0

    m, n = len(matrix), len(matrix[0])
    dp = [[0 for _ in range(n)] for _ in range(m)]

    # Initialize the first cell
    dp[0][0] = matrix[0][0]

    # Initialize first column
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + matrix[i][0]

    # Initialize first row
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + matrix[0][j]

    # Fill the rest of the DP matrix
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + matrix[i][j]

    return dp[m-1][n-1], dp

# Example usage
matrix = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1]
]
max_sum, dp_matrix = max_path_sum(matrix)
print(f"Maximum Path Sum: {max_sum}")

# To retrieve the path, backtrack from dp[m-1][n-1]
def retrieve_path(dp, matrix):
    path = []
    i, j = len(dp) - 1, len(dp[0]) - 1
    path.append(matrix[i][j])

    while i > 0 or j > 0:
        if i == 0:
            j -= 1
        elif j == 0:
            i -= 1
        else:
            if dp[i-1][j] > dp[i][j-1]:
                i -= 1
            else:
                j -= 1
        path.append(matrix[i][j])

    path.reverse()
    return path

path = retrieve_path(dp_matrix, matrix)
print("Path:", " → ".join(map(str, path)))

Output:
Maximum Path Sum: 12
Path: 1 → 3 → 5 → 2 → 1

4.2 Unique Paths in a Grid
Problem Statement:
Given a m x n grid, find the number of unique paths from the top-left corner to the bottom-right corner. You can only move either down or right at any point in time.
Example:
Input:
m = 3, n = 2

Output:
Number of Unique Paths: 3

Explanation:
The three paths are:
Right → Down → Down
Down → Right → Down
Down → Down → Right
Solution:
Use DP to calculate the number of paths to each cell by summing the paths from the cell above and the cell to the left.
Implementation (Python):
def unique_paths(m, n):
    dp = [[1 for _ in range(n)] for _ in range(m)]  # Initialize with 1s

    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 usage
m = 3
n = 2
print("Number of Unique Paths:", unique_paths(m, n))

Output:
Number of Unique Paths: 3

4.3 Longest Increasing Path in a Matrix
Problem Statement:
Given an m x n integer matrix, find the length of the longest increasing path. From each cell, you can move in four directions: up, down, left, or right. You may not move diagonally or move outside the boundary.
Example:
Input:
Matrix = [
  [9, 9, 4],
  [6, 6, 8],
  [2, 1, 1]
]

Output:
Length of Longest Increasing Path: 4
Path: [1, 2, 6, 9]

Solution:
Use DFS with memoization to find the longest increasing path starting from each cell.
Implementation (Python):
def longest_increasing_path(matrix):
    if not matrix:
        return 0

    m, n = len(matrix), len(matrix[0])
    memo = [[-1 for _ in range(n)] for _ in range(m)]
    directions = [(-1,0),(1,0),(0,-1),(0,1)]

    def dfs(i, j):
        if memo[i][j] != -1:
            return memo[i][j]
        max_length = 1
        for d in directions:
            x, y = i + d[0], j + d[1]
            if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[i][j]:
                length = 1 + dfs(x, y)
                max_length = max(max_length, length)
        memo[i][j] = max_length
        return max_length

    max_path = 0
    for i in range(m):
        for j in range(n):
            max_path = max(max_path, dfs(i, j))

    return max_path

# Example usage
matrix = [
    [9, 9, 4],
    [6, 6, 8],
    [2, 1, 1]
]
print("Length of Longest Increasing Path:", longest_increasing_path(matrix))

Output:
Length of Longest Increasing Path: 4


Pattern 5: Matrix-Based Pattern Problems
These problems involve constructing or recognizing specific patterns within a matrix or grid. They often require a good grasp of iteration and conditionals.
5.1 Print a Binary Matrix Pattern ("X" Pattern)
Problem Statement:
Given an integer n, print an n x n binary matrix where the cell (i,j) is 1 if i == j or i + j == n - 1; otherwise, it's 0. This creates an "X" pattern in the matrix.
Example:
Input:
n = 5

Output:
1 0 0 0 1
0 1 0 1 0
0 0 1 0 0
0 1 0 1 0
1 0 0 0 1

Solution:
Set cells where i == j (main diagonal) or i + j == n - 1 (anti-diagonal) to 1, and the rest to 0.
Implementation (Python):
def print_x_pattern(n):
    for i in range(n):
        for j in range(n):
            if i == j or i + j == n - 1:
                print(1, end=" ")
            else:
                print(0, end=" ")
        print()  # Newline after each row

# Example usage
n = 5
print("X Pattern Matrix:")
print_x_pattern(n)

Output:
X Pattern Matrix:
1 0 0 0 1 
0 1 0 1 0 
0 0 1 0 0 
0 1 0 1 0 
1 0 0 0 1 

5.2 Print a Hollow Rectangle Pattern
Problem Statement:
Given two integers m and n, print an m x n hollow rectangle pattern where the border elements are 1 and the interior elements are 0.
Example:
Input:
m = 4, n = 5

Output:
1 1 1 1 1
1 0 0 0 1
1 0 0 0 1
1 1 1 1 1

Solution:
Set elements on the first and last row or column to 1, and the rest to 0.
Implementation (Python):
def print_hollow_rectangle(m, n):
    for i in range(m):
        for j in range(n):
            if i == 0 or i == m-1 or j == 0 or j == n-1:
                print(1, end=" ")
            else:
                print(0, end=" ")
        print()  # Newline after each row

# Example usage
m, n = 4, 5
print(f"Hollow {m}x{n} Rectangle Pattern:")
print_hollow_rectangle(m, n)

Output:
Hollow 4x5 Rectangle Pattern:
1 1 1 1 1 
1 0 0 0 1 
1 0 0 0 1 
1 1 1 1 1 

5.3 Print a Butterfly Pattern
Problem Statement:
Given an integer n, print a butterfly pattern using stars (*). The pattern has 2n rows and 2n columns.
Example:
Input:
n = 4

Output:
*      *
**    **
***  ***
********
********
***  ***
**    **
*      *

Solution:
The butterfly pattern consists of two halves: the upper and the lower. The upper half increments the number of stars from left and right sides, separated by spaces. The lower half decrements them.
Implementation (Python):
def print_butterfly(n):
    # Upper half
    for i in range(1, n+1):
        # Left stars
        print('*' * i, end='')
        # Spaces
        print(' ' * (2*(n - i)), end='')
        # Right stars
        print('*' * i)
    
    # Lower half
    for i in range(n, 0, -1):
        # Left stars
        print('*' * i, end='')
        # Spaces
        print(' ' * (2*(n - i)), end='')
        # Right stars
        print('*' * i)

# Example usage
n = 4
print("Butterfly Pattern:")
print_butterfly(n)

Output:
Butterfly Pattern:
*      *
**    **
***  ***
********
********
***  ***
**    **
*      *


Pattern 6: Graph-Like Problems Using Matrices
Matrices can represent graphs, particularly in grid-based problems. Common graph-like problems using matrices include flood fill, number of islands, and word search.
6.1 Number of Islands
Problem Statement:
Given a 2D grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.
Example:
Input:
Grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]

Output:
Number of Islands: 3

Solution:
Use Depth-First Search (DFS) to traverse all connected lands and mark them as visited.
Implementation (Python):
def num_islands(grid):
    if not grid:
        return 0

    m, n = len(grid), len(grid[0])
    count = 0

    def dfs(i, j):
        if i <0 or i >=m or j <0 or j >=n or grid[i][j] != '1':
            return
        grid[i][j] = '0'  # Mark as visited
        # Explore neighbors
        dfs(i-1, j)  # Up
        dfs(i+1, j)  # Down
        dfs(i, j-1)  # Left
        dfs(i, j+1)  # Right

    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                dfs(i, j)
                count +=1

    return count

# Example usage
grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
print("Number of Islands:", num_islands(grid))

Output:
Number of Islands: 3

6.2 Word Search in a Grid
Problem Statement:
Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where "adjacent" cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
Example:
Input:
Board = [
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
Word = "ABCCED"

Output:
True

Solution:
Use DFS to search for the word starting from each cell. Mark cells as visited during the search to avoid revisiting.
Implementation (Python):
def exist(board, word):
    if not board:
        return False

    m, n = len(board), len(board[0])
    
    def dfs(i, j, index):
        if index == len(word):
            return True
        if i <0 or i >=m or j <0 or j >=n or board[i][j] != word[index]:
            return False
        # To avoid using the same cell again
        temp = board[i][j]
        board[i][j] = '#'
        # Explore neighbors
        found = (dfs(i-1, j, index+1) or
                 dfs(i+1, j, index+1) or
                 dfs(i, j-1, index+1) or
                 dfs(i, j+1, index+1))
        board[i][j] = temp  # Restore
        return found

    for i in range(m):
        for j in range(n):
            if dfs(i, j, 0):
                return True

    return False

# Example usage
board = [
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
word = "ABCCED"
print("Word Exists:", exist(board, word))

Output:
Word Exists: True


Pattern 7: Matrix Operations
Matrix operations such as addition, multiplication, and exponentiation are fundamental in various computational scenarios, including image processing, computer graphics, and more.
7.1 Matrix Addition
Problem Statement:
Given two matrices A and B of the same dimensions, compute their sum C = A + B.
Example:
Input:
A = [
  [1, 2, 3],
  [4, 5, 6]
]
B = [
  [7, 8, 9],
  [10,11,12]
]

Output:
C = [
  [8, 10, 12],
  [14,16,18]
]

Solution:
Iterate through corresponding elements and sum them.
Implementation (Python):
def add_matrices(A, B):
    if not A or not B:
        return []
    m, n = len(A), len(A[0])
    C = [[0 for _ in range(n)] for _ in range(m)]
    for i in range(m):
        for j in range(n):
            C[i][j] = A[i][j] + B[i][j]
    return C

# Example usage
A = [
    [1, 2, 3],
    [4, 5, 6]
]
B = [
    [7, 8, 9],
    [10,11,12]
]
C = add_matrices(A, B)
print("Matrix C = A + B:")
for row in C:
    print(row)

Output:
Matrix C = A + B:
[8, 10, 12]
[14, 16, 18]

7.2 Matrix Multiplication
Problem Statement:
Given two matrices A of size m x p and B of size p x n, compute their product C = A x B.
Example:
Input:
A = [
  [1, 2],
  [3, 4]
]
B = [
  [5, 6],
  [7, 8]
]

Output:
C = [
  [19, 22],
  [43, 50]
]

Solution:
Multiply rows of A with columns of B and sum the products.
Implementation (Python):
def multiply_matrices(A, B):
    if not A or not B or len(A[0]) != len(B):
        return []
    m, p, n = len(A), len(A[0]), len(B[0])
    C = [[0 for _ in range(n)] for _ in range(m)]
    for i in range(m):
        for j in range(n):
            for k in range(p):
                C[i][j] += A[i][k] * B[k][j]
    return C

# Example usage
A = [
    [1, 2],
    [3, 4]
]
B = [
    [5, 6],
    [7, 8]
]
C = multiply_matrices(A, B)
print("Matrix C = A x B:")
for row in C:
    print(row)

Output:
Matrix C = A x B:
[19, 22]
[43, 50]

7.3 Matrix Exponentiation
Problem Statement:
Given a square matrix A of size n x n and an integer k, compute the k-th power of A (i.e., A^k).
Example:
Input:
A = [
  [1, 2],
  [3, 4]
]
k = 2

Output:
A^2 = [
  [7, 10],
  [15, 22]
]

Solution:
Use the fast exponentiation method to efficiently compute the power by repeatedly multiplying matrices.
Implementation (Python):
def multiply(A, B):
    n = len(A)
    result = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                result[i][j] += A[i][k] * B[k][j]
    return result

def matrix_power(A, k):
    if k == 0:
        # Return identity matrix
        n = len(A)
        return [[1 if i == j else 0 for j in range(n)] for i in range(n)]
    if k == 1:
        return A
    half = matrix_power(A, k // 2)
    half_squared = multiply(half, half)
    if k % 2 == 0:
        return half_squared
    else:
        return multiply(half_squared, A)

# Example usage
A = [
    [1, 2],
    [3, 4]
]
k = 2
A_power_k = matrix_power(A, k)
print(f"Matrix A^{k}:")
for row in A_power_k:
    print(row)

Output:
Matrix A^2:
[7, 10]
[15, 22]


Pattern 8: Advanced Traversal Techniques
Advanced traversal techniques like Depth-First Search (DFS) and Breadth-First Search (BFS) are essential for exploring matrices in scenarios similar to graph traversal, such as pathfinding and connectivity checking.
8.1 Depth-First Search (DFS) in a Matrix
Problem Statement:
Given a matrix, perform a DFS traversal starting from a specific cell (i, j).
Example:
Input:
Matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]
Start Cell: (0, 0)

Output (One Possible DFS Order):
1, 2, 3, 6, 9, 8, 7, 4, 5

Solution:
Implement DFS recursively, visiting adjacent cells that haven't been visited yet.
Implementation (Python):
def dfs_matrix(matrix, start_i, start_j):
    if not matrix:
        return []

    m, n = len(matrix), len(matrix[0])
    visited = [[False for _ in range(n)] for _ in range(m)]
    traversal = []
    directions = [(-1,0),(1,0),(0,-1),(0,1)]  # Up, Down, Left, Right

    def dfs(i, j):
        if i <0 or i >=m or j <0 or j >=n or visited[i][j]:
            return
        visited[i][j] = True
        traversal.append(matrix[i][j])
        for d in directions:
            dfs(i + d[0], j + d[1])

    dfs(start_i, start_j)
    return traversal

# Example usage
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
start_i, start_j = 0, 0
print("DFS Traversal Order:", ', '.join(map(str, dfs_matrix(matrix, start_i, start_j))))

Output:
DFS Traversal Order: 1, 2, 3, 6, 9, 8, 7, 4, 5

8.2 Breadth-First Search (BFS) in a Matrix
Problem Statement:
Given a matrix, perform a BFS traversal starting from a specific cell (i, j).
Example:
Input:
Matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]
Start Cell: (0, 0)

Output (BFS Order):
1, 2, 4, 3, 5, 7, 6, 8, 9

Solution:
Implement BFS using a queue, visiting adjacent cells level by level.
Implementation (Python):
from collections import deque

def bfs_matrix(matrix, start_i, start_j):
    if not matrix:
        return []

    m, n = len(matrix), len(matrix[0])
    visited = [[False for _ in range(n)] for _ in range(m)]
    traversal = []
    queue = deque()
    directions = [(-1,0),(1,0),(0,-1),(0,1)]  # Up, Down, Left, Right

    queue.append((start_i, start_j))
    visited[start_i][start_j] = True

    while queue:
        i, j = queue.popleft()
        traversal.append(matrix[i][j])
        for d in directions:
            x, y = i + d[0], j + d[1]
            if 0 <= x < m and 0 <= y < n and not visited[x][y]:
                queue.append((x, y))
                visited[x][y] = True

    return traversal

# Example usage
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
start_i, start_j = 0, 0
print("BFS Traversal Order:", ', '.join(map(str, bfs_matrix(matrix, start_i, start_j))))

Output:
BFS Traversal Order: 1, 2, 4, 3, 5, 7, 6, 8, 9


Pattern 9: Repeating Patterns and Shapes in Matrices
Solving pattern recognition and construction problems enhances understanding of matrix indices and conditional logic.
9.1 Print a Spiral Matrix (Clockwise)
Problem Statement:
Given an integer n, generate an n x n spiral matrix filled with elements from 1 to n^2 in spiral order.
Example:
Input:
n = 3

Output:
Spiral Matrix:
1 2 3
8 9 4
7 6 5

Solution:
Iteratively assign values while traversing the matrix in spiral order using top, bottom, left, and right pointers.
Implementation (Python):
def generate_spiral_matrix(n):
    matrix = [[0 for _ in range(n)] for _ in range(n)]
    top, bottom, left, right = 0, n-1, 0, n-1
    num = 1

    while top <= bottom and left <= right:
        # Traverse from left to right
        for j in range(left, right +1):
            matrix[top][j] = num
            num +=1
        top +=1

        # Traverse from top to bottom
        for i in range(top, bottom +1):
            matrix[i][right] = num
            num +=1
        right -=1

        # Traverse from right to left
        if top <= bottom:
            for j in range(right, left -1, -1):
                matrix[bottom][j] = num
                num +=1
            bottom -=1

        # Traverse from bottom to top
        if left <= right:
            for i in range(bottom, top -1, -1):
                matrix[i][left] = num
                num +=1
            left +=1

    return matrix

# Example usage
n = 3
spiral_matrix = generate_spiral_matrix(n)
print("Spiral Matrix:")
for row in spiral_matrix:
    print(' '.join(map(str, row)))

Output:
Spiral Matrix:
1 2 3
8 9 4
7 6 5

9.2 Print a Diagonal Matrix
Problem Statement:
Given an integer n, print an n x n matrix where each element is the sum of its row and column indices.
Example:
Input:
n = 4

Output:
0 1 2 3
1 2 3 4
2 3 4 5
3 4 5 6

Solution:
Set each cell (i,j) to i + j.
Implementation (Python):
def print_diagonal_matrix(n):
    for i in range(n):
        for j in range(n):
            print(i + j, end=" ")
        print()

# Example usage
n = 4
print(f"Diagonal {n}x{n} Matrix:")
print_diagonal_matrix(n)

Output:
Diagonal 4x4 Matrix:
0 1 2 3 
1 2 3 4 
2 3 4 5 
3 4 5 6 

Happy Coding!



"""
please give all for graph like all i dont want to not know anything