Complete DSA Series Part 5: Matrices - Special & Sparse

Matrices are two-dimensional arrays that play a crucial role in computer science, mathematics, and engineering. Understanding efficient matrix storage and operations is essential for graphics, machine learning, scientific computing, and solving system of linear equations.

Matrix 2D array structure showing row-major and column-major memory layouts — Matrix as a 2D array — elements can be stored in row-major or column-major order in contiguous memory

                            
                            Key Insight: Special matrices have patterns that allow us to store n×n elements using much less than n² space. This optimization is critical when dealing with large matrices in real-world applications.
                        

2D Array Representation

In memory, 2D arrays can be stored in two ways: Row-Major Order (C, Python) or Column-Major Order (Fortran, MATLAB).

# 2D Array Basics and Memory Layout
import numpy as np

# Creating a 2D array (matrix)
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

# Dimensions
rows = len(matrix)
cols = len(matrix[0])
print(f"Matrix dimensions: {rows}x{cols}")

# Accessing elements: matrix[row][col]
print(f"Element at (1,2): {matrix[1][2]}")  # 6

# Row-Major Order: Elements stored row by row
# Memory layout: [1, 2, 3, 4, 5, 6, 7, 8, 9]
# Index formula: index = row * num_cols + col

def row_major_index(row, col, num_cols):
    """Convert 2D index to 1D index (row-major)"""
    return row * num_cols + col

# Column-Major Order: Elements stored column by column
# Memory layout: [1, 4, 7, 2, 5, 8, 3, 6, 9]
# Index formula: index = col * num_rows + row

def col_major_index(row, col, num_rows):
    """Convert 2D index to 1D index (column-major)"""
    return col * num_rows + row

# Demonstrate both orderings
print("\nRow-Major vs Column-Major:")
for i in range(3):
    for j in range(3):
        rm = row_major_index(i, j, 3)
        cm = col_major_index(i, j, 3)
        print(f"({i},{j}): Row-Major idx={rm}, Col-Major idx={cm}")

#include <iostream>
using namespace std;

int main() {
    // Creating a 2D array (matrix)
    int matrix[3][3] = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    
    int rows = 3, cols = 3;
    cout << "Matrix dimensions: " << rows << "x" << cols << endl;
    
    // Accessing elements: matrix[row][col]
    cout << "Element at (1,2): " << matrix[1][2] << endl;  // 6
    
    // Row-Major Order (C++ default): Elements stored row by row
    // Memory layout: [1, 2, 3, 4, 5, 6, 7, 8, 9]
    
    // Convert 2D to 1D index (row-major)
    auto rowMajorIndex = [](int row, int col, int numCols) {
        return row * numCols + col;
    };
    
    // Convert 2D to 1D index (column-major)
    auto colMajorIndex = [](int row, int col, int numRows) {
        return col * numRows + row;
    };
    
    cout << "\nRow-Major vs Column-Major:" << endl;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            int rm = rowMajorIndex(i, j, 3);
            int cm = colMajorIndex(i, j, 3);
            cout << "(" << i << "," << j << "): "
                 << "Row-Major idx=" << rm << ", "
                 << "Col-Major idx=" << cm << endl;
        }
    }
    
    return 0;
}

public class MatrixBasics {
    public static void main(String[] args) {
        // Creating a 2D array (matrix)
        int[][] matrix = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };
        
        int rows = matrix.length;
        int cols = matrix[0].length;
        System.out.println("Matrix dimensions: " + rows + "x" + cols);
        
        // Accessing elements: matrix[row][col]
        System.out.println("Element at (1,2): " + matrix[1][2]);  // 6
        
        // Row-Major Order (Java default): Elements stored row by row
        // Memory layout: [1, 2, 3, 4, 5, 6, 7, 8, 9]
        
        System.out.println("\nRow-Major vs Column-Major:");
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                int rm = rowMajorIndex(i, j, 3);
                int cm = colMajorIndex(i, j, 3);
                System.out.println("(" + i + "," + j + "): " +
                    "Row-Major idx=" + rm + ", Col-Major idx=" + cm);
            }
        }
    }
    
    // Convert 2D to 1D index (row-major)
    static int rowMajorIndex(int row, int col, int numCols) {
        return row * numCols + col;
    }
    
    // Convert 2D to 1D index (column-major)
    static int colMajorIndex(int row, int col, int numRows) {
        return col * numRows + row;
    }
}

Special Matrices

Special matrices exploit structural patterns to compress storage from \(O(n^2)\) to \(O(n)\). The key insight: if most elements are zero or can be computed from a formula (e.g., \(M[i][j] = M[j][i]\) for symmetric matrices), store only the unique non-trivial elements and reconstruct the rest on access. This is critical in scientific computing, computer graphics (transformation matrices), and machine learning (covariance matrices, weight sparsity).

Diagonal Matrix

A diagonal matrix has non-zero elements only on the main diagonal (where \(i = j\)). Instead of storing \(n^2\) elements, we only need \(n\) elements. Real-world example: scaling matrices in computer graphics — a 4×4 diagonal matrix scales x, y, z coordinates independently. Multiplication by a diagonal matrix is \(O(n)\) instead of \(O(n^2)\) since each row is just multiplied by the corresponding diagonal element.

# Diagonal Matrix Implementation
# Only diagonal elements are non-zero: M[i][j] != 0 only when i == j
# Space: O(n) instead of O(n²)

class DiagonalMatrix:
    def __init__(self, n):
        self.n = n
        self.diagonal = [0] * n  # Only store diagonal elements
    
    def set(self, i, j, value):
        """Set element at position (i, j)"""
        if i < 0 or i >= self.n or j < 0 or j >= self.n:
            raise IndexError("Index out of bounds")
        if i == j:
            self.diagonal[i] = value
        elif value != 0:
            raise ValueError("Non-diagonal elements must be 0")
    
    def get(self, i, j):
        """Get element at position (i, j)"""
        if i < 0 or i >= self.n or j < 0 or j >= self.n:
            raise IndexError("Index out of bounds")
        if i == j:
            return self.diagonal[i]
        return 0
    
    def display(self):
        """Display full matrix"""
        for i in range(self.n):
            row = [self.get(i, j) for j in range(self.n)]
            print(row)
    
    def space_saved(self):
        """Calculate space savings"""
        full_space = self.n * self.n
        actual_space = self.n
        return f"Saved {full_space - actual_space} elements ({100*(1 - actual_space/full_space):.1f}%)"

# Test Diagonal Matrix
dm = DiagonalMatrix(4)
dm.set(0, 0, 5)
dm.set(1, 1, 10)
dm.set(2, 2, 15)
dm.set(3, 3, 20)

print("Diagonal Matrix:")
dm.display()
print(f"\n{dm.space_saved()}")
# Output: Saved 12 elements (75.0%)

#include <iostream>
#include <vector>
#include <stdexcept>
using namespace std;

class DiagonalMatrix {
private:
    int n;
    vector<int> diagonal;  // Only store diagonal elements
    
public:
    DiagonalMatrix(int size) : n(size), diagonal(size, 0) {}
    
    void set(int i, int j, int value) {
        if (i < 0 || i >= n || j < 0 || j >= n)
            throw out_of_range("Index out of bounds");
        if (i == j)
            diagonal[i] = value;
        else if (value != 0)
            throw invalid_argument("Non-diagonal elements must be 0");
    }
    
    int get(int i, int j) {
        if (i < 0 || i >= n || j < 0 || j >= n)
            throw out_of_range("Index out of bounds");
        return (i == j) ? diagonal[i] : 0;
    }
    
    void display() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cout << get(i, j) << " ";
            }
            cout << endl;
        }
    }
    
    void spaceSaved() {
        int fullSpace = n * n;
        int actualSpace = n;
        double savings = 100.0 * (1 - (double)actualSpace / fullSpace);
        cout << "Saved " << (fullSpace - actualSpace) 
             << " elements (" << savings << "%)" << endl;
    }
};

int main() {
    DiagonalMatrix dm(4);
    dm.set(0, 0, 5);
    dm.set(1, 1, 10);
    dm.set(2, 2, 15);
    dm.set(3, 3, 20);
    
    cout << "Diagonal Matrix:" << endl;
    dm.display();
    dm.spaceSaved();  // Saved 12 elements (75%)
    return 0;
}

public class DiagonalMatrix {
    private int n;
    private int[] diagonal;  // Only store diagonal elements
    
    public DiagonalMatrix(int size) {
        this.n = size;
        this.diagonal = new int[size];
    }
    
    public void set(int i, int j, int value) {
        if (i < 0 || i >= n || j < 0 || j >= n)
            throw new IndexOutOfBoundsException("Index out of bounds");
        if (i == j)
            diagonal[i] = value;
        else if (value != 0)
            throw new IllegalArgumentException("Non-diagonal elements must be 0");
    }
    
    public int get(int i, int j) {
        if (i < 0 || i >= n || j < 0 || j >= n)
            throw new IndexOutOfBoundsException("Index out of bounds");
        return (i == j) ? diagonal[i] : 0;
    }
    
    public void display() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(get(i, j) + " ");
            }
            System.out.println();
        }
    }
    
    public void spaceSaved() {
        int fullSpace = n * n;
        int actualSpace = n;
        double savings = 100.0 * (1 - (double)actualSpace / fullSpace);
        System.out.printf("Saved %d elements (%.1f%%)%n", 
            fullSpace - actualSpace, savings);
    }
    
    public static void main(String[] args) {
        DiagonalMatrix dm = new DiagonalMatrix(4);
        dm.set(0, 0, 5);
        dm.set(1, 1, 10);
        dm.set(2, 2, 15);
        dm.set(3, 3, 20);
        
        System.out.println("Diagonal Matrix:");
        dm.display();
        dm.spaceSaved();  // Saved 12 elements (75.0%)
    }
}

Triangular Matrices

Triangular matrices have non-zero elements only above (upper) or below (lower) the diagonal. Storage: \(n(n+1)/2\) elements instead of \(n^2\). Why they matter: Gaussian elimination produces upper triangular form, LU decomposition splits any matrix into lower × upper triangular, and Cholesky decomposition (for symmetric positive definite matrices) uses \(L \cdot L^T\). Solving \(Ax = b\) with a triangular matrix takes only \(O(n^2)\) via back/forward substitution — much faster than the general \(O(n^3)\).

# Lower Triangular Matrix Implementation
# Non-zero elements only at or below diagonal: M[i][j] != 0 only when i >= j
# Number of elements: n(n+1)/2

class LowerTriangularMatrix:
    def __init__(self, n):
        self.n = n
        # Store elements row by row: row 0 has 1 element, row 1 has 2, etc.
        size = n * (n + 1) // 2
        self.data = [0] * size
    
    def _index(self, i, j):
        """Map 2D index to 1D array index (row-major for lower triangular)"""
        # Elements before row i: 1 + 2 + ... + i = i*(i+1)/2
        # Then add j for column position
        return i * (i + 1) // 2 + j
    
    def set(self, i, j, value):
        if i >= j:  # Lower triangular includes diagonal
            self.data[self._index(i, j)] = value
        elif value != 0:
            raise ValueError("Upper triangular elements must be 0")
    
    def get(self, i, j):
        if i >= j:
            return self.data[self._index(i, j)]
        return 0
    
    def display(self):
        for i in range(self.n):
            row = [self.get(i, j) for j in range(self.n)]
            print(row)

# Upper Triangular Matrix Implementation
# Non-zero elements only at or above diagonal: M[i][j] != 0 only when i <= j

class UpperTriangularMatrix:
    def __init__(self, n):
        self.n = n
        size = n * (n + 1) // 2
        self.data = [0] * size
    
    def _index(self, i, j):
        """Map 2D index to 1D array index (row-major for upper triangular)"""
        # Row i starts at index: n + (n-1) + ... + (n-i+1) = i*n - i*(i-1)/2
        # Then add (j - i) for column offset within the row
        return i * self.n - i * (i - 1) // 2 + (j - i)
    
    def set(self, i, j, value):
        if i <= j:  # Upper triangular includes diagonal
            self.data[self._index(i, j)] = value
        elif value != 0:
            raise ValueError("Lower triangular elements must be 0")
    
    def get(self, i, j):
        if i <= j:
            return self.data[self._index(i, j)]
        return 0
    
    def display(self):
        for i in range(self.n):
            row = [self.get(i, j) for j in range(self.n)]
            print(row)

# Test Lower Triangular
print("Lower Triangular Matrix:")
ltm = LowerTriangularMatrix(4)
val = 1
for i in range(4):
    for j in range(i + 1):
        ltm.set(i, j, val)
        val += 1
ltm.display()

# Test Upper Triangular
print("\nUpper Triangular Matrix:")
utm = UpperTriangularMatrix(4)
val = 1
for i in range(4):
    for j in range(i, 4):
        utm.set(i, j, val)
        val += 1
utm.display()

#include <iostream>
#include <vector>
using namespace std;

class LowerTriangularMatrix {
private:
    int n;
    vector<int> data;
    
    int index(int i, int j) {
        return i * (i + 1) / 2 + j;
    }
    
public:
    LowerTriangularMatrix(int size) : n(size) {
        int sz = size * (size + 1) / 2;
        data.resize(sz, 0);
    }
    
    void set(int i, int j, int value) {
        if (i >= j) data[index(i, j)] = value;
        else if (value != 0)
            throw invalid_argument("Upper part must be 0");
    }
    
    int get(int i, int j) {
        return (i >= j) ? data[index(i, j)] : 0;
    }
    
    void display() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                cout << get(i, j) << " ";
            cout << endl;
        }
    }
};

class UpperTriangularMatrix {
private:
    int n;
    vector<int> data;
    
    int index(int i, int j) {
        return i * n - i * (i - 1) / 2 + (j - i);
    }
    
public:
    UpperTriangularMatrix(int size) : n(size) {
        int sz = size * (size + 1) / 2;
        data.resize(sz, 0);
    }
    
    void set(int i, int j, int value) {
        if (i <= j) data[index(i, j)] = value;
        else if (value != 0)
            throw invalid_argument("Lower part must be 0");
    }
    
    int get(int i, int j) {
        return (i <= j) ? data[index(i, j)] : 0;
    }
    
    void display() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                cout << get(i, j) << " ";
            cout << endl;
        }
    }
};

int main() {
    // Test Lower Triangular
    cout << "Lower Triangular Matrix:" << endl;
    LowerTriangularMatrix ltm(4);
    int val = 1;
    for (int i = 0; i < 4; i++)
        for (int j = 0; j <= i; j++)
            ltm.set(i, j, val++);
    ltm.display();
    
    // Test Upper Triangular
    cout << "\nUpper Triangular Matrix:" << endl;
    UpperTriangularMatrix utm(4);
    val = 1;
    for (int i = 0; i < 4; i++)
        for (int j = i; j < 4; j++)
            utm.set(i, j, val++);
    utm.display();
    
    return 0;
}

public class TriangularMatrices {
    // Lower Triangular Matrix
    static class LowerTriangularMatrix {
        private int n;
        private int[] data;
        
        public LowerTriangularMatrix(int size) {
            this.n = size;
            this.data = new int[size * (size + 1) / 2];
        }
        
        private int index(int i, int j) {
            return i * (i + 1) / 2 + j;
        }
        
        public void set(int i, int j, int value) {
            if (i >= j) data[index(i, j)] = value;
            else if (value != 0)
                throw new IllegalArgumentException("Upper part must be 0");
        }
        
        public int get(int i, int j) {
            return (i >= j) ? data[index(i, j)] : 0;
        }
        
        public void display() {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++)
                    System.out.print(get(i, j) + " ");
                System.out.println();
            }
        }
    }
    
    // Upper Triangular Matrix
    static class UpperTriangularMatrix {
        private int n;
        private int[] data;
        
        public UpperTriangularMatrix(int size) {
            this.n = size;
            this.data = new int[size * (size + 1) / 2];
        }
        
        private int index(int i, int j) {
            return i * n - i * (i - 1) / 2 + (j - i);
        }
        
        public void set(int i, int j, int value) {
            if (i <= j) data[index(i, j)] = value;
            else if (value != 0)
                throw new IllegalArgumentException("Lower part must be 0");
        }
        
        public int get(int i, int j) {
            return (i <= j) ? data[index(i, j)] : 0;
        }
        
        public void display() {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++)
                    System.out.print(get(i, j) + " ");
                System.out.println();
            }
        }
    }
    
    public static void main(String[] args) {
        // Test Lower Triangular
        System.out.println("Lower Triangular Matrix:");
        LowerTriangularMatrix ltm = new LowerTriangularMatrix(4);
        int val = 1;
        for (int i = 0; i < 4; i++)
            for (int j = 0; j <= i; j++)
                ltm.set(i, j, val++);
        ltm.display();
        
        // Test Upper Triangular
        System.out.println("\nUpper Triangular Matrix:");
        UpperTriangularMatrix utm = new UpperTriangularMatrix(4);
        val = 1;
        for (int i = 0; i < 4; i++)
            for (int j = i; j < 4; j++)
                utm.set(i, j, val++);
        utm.display();
    }
}

Symmetric Matrix

A symmetric matrix satisfies M[i][j] = M[j][i]. We only need to store the lower (or upper) triangular portion, requiring n(n+1)/2 elements.

# Symmetric Matrix Implementation
# M[i][j] = M[j][i] for all i, j
# Store only lower triangular part: n(n+1)/2 elements

class SymmetricMatrix:
    def __init__(self, n):
        self.n = n
        size = n * (n + 1) // 2
        self.data = [0] * size
    
    def _index(self, i, j):
        """Store lower triangular part in row-major order"""
        if i < j:
            i, j = j, i  # Swap to get lower triangular index
        return i * (i + 1) // 2 + j
    
    def set(self, i, j, value):
        """Setting M[i][j] automatically sets M[j][i]"""
        if 0 <= i < self.n and 0 <= j < self.n:
            self.data[self._index(i, j)] = value
    
    def get(self, i, j):
        if 0 <= i < self.n and 0 <= j < self.n:
            return self.data[self._index(i, j)]
        raise IndexError("Index out of bounds")
    
    def display(self):
        for i in range(self.n):
            row = [self.get(i, j) for j in range(self.n)]
            print(row)
    
    def is_symmetric(self):
        """Verify symmetry"""
        for i in range(self.n):
            for j in range(self.n):
                if self.get(i, j) != self.get(j, i):
                    return False
        return True

# Test Symmetric Matrix
print("Symmetric Matrix:")
sm = SymmetricMatrix(4)
# Set lower triangular elements
sm.set(0, 0, 1)
sm.set(1, 0, 2)
sm.set(1, 1, 3)
sm.set(2, 0, 4)
sm.set(2, 1, 5)
sm.set(2, 2, 6)
sm.set(3, 0, 7)
sm.set(3, 1, 8)
sm.set(3, 2, 9)
sm.set(3, 3, 10)

sm.display()
print(f"Is symmetric: {sm.is_symmetric()}")  # True

# Verify: M[1][0] should equal M[0][1]
print(f"M[1][0] = {sm.get(1, 0)}, M[0][1] = {sm.get(0, 1)}")

#include <iostream>
#include <vector>
using namespace std;

class SymmetricMatrix {
private:
    int n;
    vector<int> data;
    
    int index(int i, int j) {
        if (i < j) swap(i, j);  // Use lower triangular
        return i * (i + 1) / 2 + j;
    }
    
public:
    SymmetricMatrix(int size) : n(size) {
        data.resize(size * (size + 1) / 2, 0);
    }
    
    void set(int i, int j, int value) {
        if (i >= 0 && i < n && j >= 0 && j < n)
            data[index(i, j)] = value;
    }
    
    int get(int i, int j) {
        if (i >= 0 && i < n && j >= 0 && j < n)
            return data[index(i, j)];
        throw out_of_range("Index out of bounds");
    }
    
    void display() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                cout << get(i, j) << " ";
            cout << endl;
        }
    }
    
    bool isSymmetric() {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (get(i, j) != get(j, i))
                    return false;
        return true;
    }
};

int main() {
    cout << "Symmetric Matrix:" << endl;
    SymmetricMatrix sm(4);
    
    // Set lower triangular elements
    sm.set(0, 0, 1);
    sm.set(1, 0, 2); sm.set(1, 1, 3);
    sm.set(2, 0, 4); sm.set(2, 1, 5); sm.set(2, 2, 6);
    sm.set(3, 0, 7); sm.set(3, 1, 8); sm.set(3, 2, 9); sm.set(3, 3, 10);
    
    sm.display();
    cout << "Is symmetric: " << (sm.isSymmetric() ? "true" : "false") << endl;
    
    // Verify: M[1][0] should equal M[0][1]
    cout << "M[1][0] = " << sm.get(1, 0) << ", M[0][1] = " << sm.get(0, 1) << endl;
    
    return 0;
}

public class SymmetricMatrix {
    private int n;
    private int[] data;
    
    public SymmetricMatrix(int size) {
        this.n = size;
        this.data = new int[size * (size + 1) / 2];
    }
    
    private int index(int i, int j) {
        if (i < j) { int temp = i; i = j; j = temp; }  // Use lower triangular
        return i * (i + 1) / 2 + j;
    }
    
    public void set(int i, int j, int value) {
        if (i >= 0 && i < n && j >= 0 && j < n)
            data[index(i, j)] = value;
    }
    
    public int get(int i, int j) {
        if (i >= 0 && i < n && j >= 0 && j < n)
            return data[index(i, j)];
        throw new IndexOutOfBoundsException("Index out of bounds");
    }
    
    public void display() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                System.out.print(get(i, j) + " ");
            System.out.println();
        }
    }
    
    public boolean isSymmetric() {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (get(i, j) != get(j, i))
                    return false;
        return true;
    }
    
    public static void main(String[] args) {
        System.out.println("Symmetric Matrix:");
        SymmetricMatrix sm = new SymmetricMatrix(4);
        
        // Set lower triangular elements
        sm.set(0, 0, 1);
        sm.set(1, 0, 2); sm.set(1, 1, 3);
        sm.set(2, 0, 4); sm.set(2, 1, 5); sm.set(2, 2, 6);
        sm.set(3, 0, 7); sm.set(3, 1, 8); sm.set(3, 2, 9); sm.set(3, 3, 10);
        
        sm.display();
        System.out.println("Is symmetric: " + sm.isSymmetric());
        
        // Verify: M[1][0] should equal M[0][1]
        System.out.println("M[1][0] = " + sm.get(1, 0) + ", M[0][1] = " + sm.get(0, 1));
    }
}

Tri-diagonal Matrix

A tri-diagonal matrix has non-zero elements only on the main diagonal and the diagonals immediately above and below it. It requires only 3n-2 elements.

# Tri-diagonal Matrix Implementation
# Non-zero elements only on: main diagonal, super-diagonal, sub-diagonal
# |i - j| <= 1
# Elements: 3n - 2

class TridiagonalMatrix:
    def __init__(self, n):
        self.n = n
        # Store: lower diagonal (n-1), main diagonal (n), upper diagonal (n-1)
        # Total: 3n - 2 elements
        self.lower = [0] * (n - 1)   # Sub-diagonal
        self.main = [0] * n           # Main diagonal
        self.upper = [0] * (n - 1)    # Super-diagonal
    
    def set(self, i, j, value):
        if i == j:  # Main diagonal
            self.main[i] = value
        elif i == j + 1:  # Lower diagonal (i - j = 1)
            self.lower[j] = value
        elif i == j - 1:  # Upper diagonal (j - i = 1)
            self.upper[i] = value
        elif value != 0:
            raise ValueError("Element not on tri-diagonal")
    
    def get(self, i, j):
        if i == j:
            return self.main[i]
        elif i == j + 1:
            return self.lower[j]
        elif i == j - 1:
            return self.upper[i]
        return 0
    
    def display(self):
        for i in range(self.n):
            row = [self.get(i, j) for j in range(self.n)]
            print(row)
    
    def space_efficiency(self):
        full = self.n * self.n
        actual = 3 * self.n - 2
        return f"Elements: {actual} vs {full} ({100*actual/full:.1f}%)"

# Test Tri-diagonal Matrix
print("Tri-diagonal Matrix:")
tm = TridiagonalMatrix(5)

# Set main diagonal
for i in range(5):
    tm.set(i, i, i * 2 + 1)

# Set lower diagonal
for i in range(4):
    tm.set(i + 1, i, -1)

# Set upper diagonal
for i in range(4):
    tm.set(i, i + 1, 1)

tm.display()
print(f"\n{tm.space_efficiency()}")

#include <iostream>
#include <vector>
using namespace std;

class TridiagonalMatrix {
private:
    int n;
    vector<int> lower;  // Sub-diagonal (n-1 elements)
    vector<int> mainDiag;  // Main diagonal (n elements)
    vector<int> upper;  // Super-diagonal (n-1 elements)
    
public:
    TridiagonalMatrix(int size) : n(size) {
        lower.resize(size - 1, 0);
        mainDiag.resize(size, 0);
        upper.resize(size - 1, 0);
    }
    
    void set(int i, int j, int value) {
        if (i == j)
            mainDiag[i] = value;
        else if (i == j + 1)
            lower[j] = value;
        else if (i == j - 1)
            upper[i] = value;
        else if (value != 0)
            throw invalid_argument("Element not on tri-diagonal");
    }
    
    int get(int i, int j) {
        if (i == j) return mainDiag[i];
        else if (i == j + 1) return lower[j];
        else if (i == j - 1) return upper[i];
        return 0;
    }
    
    void display() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                cout << get(i, j) << "\t";
            cout << endl;
        }
    }
    
    void spaceEfficiency() {
        int full = n * n;
        int actual = 3 * n - 2;
        cout << "Elements: " << actual << " vs " << full 
             << " (" << (100.0 * actual / full) << "%)" << endl;
    }
};

int main() {
    cout << "Tri-diagonal Matrix:" << endl;
    TridiagonalMatrix tm(5);
    
    // Set main diagonal
    for (int i = 0; i < 5; i++)
        tm.set(i, i, i * 2 + 1);
    
    // Set lower diagonal
    for (int i = 0; i < 4; i++)
        tm.set(i + 1, i, -1);
    
    // Set upper diagonal
    for (int i = 0; i < 4; i++)
        tm.set(i, i + 1, 1);
    
    tm.display();
    tm.spaceEfficiency();
    
    return 0;
}

public class TridiagonalMatrix {
    private int n;
    private int[] lower;    // Sub-diagonal (n-1 elements)
    private int[] mainDiag; // Main diagonal (n elements)
    private int[] upper;    // Super-diagonal (n-1 elements)
    
    public TridiagonalMatrix(int size) {
        this.n = size;
        this.lower = new int[size - 1];
        this.mainDiag = new int[size];
        this.upper = new int[size - 1];
    }
    
    public void set(int i, int j, int value) {
        if (i == j)
            mainDiag[i] = value;
        else if (i == j + 1)
            lower[j] = value;
        else if (i == j - 1)
            upper[i] = value;
        else if (value != 0)
            throw new IllegalArgumentException("Element not on tri-diagonal");
    }
    
    public int get(int i, int j) {
        if (i == j) return mainDiag[i];
        else if (i == j + 1) return lower[j];
        else if (i == j - 1) return upper[i];
        return 0;
    }
    
    public void display() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                System.out.print(get(i, j) + "\t");
            System.out.println();
        }
    }
    
    public void spaceEfficiency() {
        int full = n * n;
        int actual = 3 * n - 2;
        System.out.printf("Elements: %d vs %d (%.1f%%)%n", 
            actual, full, 100.0 * actual / full);
    }
    
    public static void main(String[] args) {
        System.out.println("Tri-diagonal Matrix:");
        TridiagonalMatrix tm = new TridiagonalMatrix(5);
        
        // Set main diagonal
        for (int i = 0; i < 5; i++)
            tm.set(i, i, i * 2 + 1);
        
        // Set lower diagonal
        for (int i = 0; i < 4; i++)
            tm.set(i + 1, i, -1);
        
        // Set upper diagonal
        for (int i = 0; i < 4; i++)
            tm.set(i, i + 1, 1);
        
        tm.display();
        tm.spaceEfficiency();
    }
}

                            Special Matrix Space Comparison
                            
                                
                                        Matrix Type
                                        Non-zero Pattern
                                        Space Required
                                        For n=100
                                    

                                
                                        Full Matrix
                                        All elements
                                        n²
                                        10,000
                                    

                                        Diagonal
                                        i = j
                                        n
                                        100
                                    

                                        Triangular
                                        i = j or i = j
                                        n(n+1)/2
                                        5,050
                                    

                                        Symmetric
                                        M[i][j] = M[j][i]
                                        n(n+1)/2
                                        5,050
                                    

                                        Tri-diagonal
                                        |i - j| = 1
                                        3n - 2
                                        298
                                    

                            
                        

Matrix Type	Non-zero Pattern	Space Required	For n=100
Full Matrix	All elements	n²	10,000
Diagonal	i = j	n	100
Triangular	i = j or i = j	n(n+1)/2	5,050
Symmetric	M[i][j] = M[j][i]	n(n+1)/2	5,050
Tri-diagonal	\|i - j\| = 1	3n - 2	298

Sparse Matrices

A sparse matrix is one where most elements are zero. When the number of non-zero elements is much smaller than n×m, storing only the non-zero elements saves significant space.

Sparse matrix with mostly zero elements and COO triplet storage format — Sparse matrix storage — only non-zero elements are stored using formats like COO (coordinate) and CSR (compressed sparse row)

Coordinate Format (COO)

The simplest sparse format stores each non-zero element with its row index, column index, and value.

# Sparse Matrix - Coordinate (COO) Format
# Store: (row, col, value) triplets for each non-zero element
# Good for: construction, conversion to other formats
# Bad for: arithmetic operations, slicing

class SparseMatrixCOO:
    def __init__(self, rows, cols):
        self.rows = rows
        self.cols = cols
        self.row_indices = []
        self.col_indices = []
        self.values = []
    
    def set(self, i, j, value):
        """Set element at (i, j)"""
        if value == 0:
            return
        
        # Check if element exists
        for idx in range(len(self.values)):
            if self.row_indices[idx] == i and self.col_indices[idx] == j:
                self.values[idx] = value
                return
        
        # Add new element
        self.row_indices.append(i)
        self.col_indices.append(j)
        self.values.append(value)
    
    def get(self, i, j):
        """Get element at (i, j)"""
        for idx in range(len(self.values)):
            if self.row_indices[idx] == i and self.col_indices[idx] == j:
                return self.values[idx]
        return 0
    
    def nnz(self):
        """Number of non-zero elements"""
        return len(self.values)
    
    def display(self):
        """Display full matrix"""
        for i in range(self.rows):
            row = [self.get(i, j) for j in range(self.cols)]
            print(row)
    
    def display_sparse(self):
        """Display sparse representation"""
        print("Row:", self.row_indices)
        print("Col:", self.col_indices)
        print("Val:", self.values)
    
    def density(self):
        total = self.rows * self.cols
        return self.nnz() / total

# Test COO Sparse Matrix
print("Sparse Matrix (COO Format):")
sparse = SparseMatrixCOO(5, 5)
sparse.set(0, 0, 1)
sparse.set(0, 4, 2)
sparse.set(1, 1, 3)
sparse.set(2, 2, 4)
sparse.set(3, 0, 5)
sparse.set(4, 3, 6)
sparse.set(4, 4, 7)

print("\nFull Matrix:")
sparse.display()
print("\nSparse Representation:")
sparse.display_sparse()
print(f"\nNon-zero elements: {sparse.nnz()}")
print(f"Density: {sparse.density():.2%}")
print(f"Space savings: {100 * (1 - 3*sparse.nnz() / (sparse.rows * sparse.cols)):.1f}%")

#include <iostream>
#include <vector>
using namespace std;

class SparseMatrixCOO {
private:
    int rows, cols;
    vector<int> rowIndices, colIndices;
    vector<int> values;
    
public:
    SparseMatrixCOO(int r, int c) : rows(r), cols(c) {}
    
    void set(int i, int j, int value) {
        if (value == 0) return;
        
        // Check if element exists
        for (size_t idx = 0; idx < values.size(); idx++) {
            if (rowIndices[idx] == i && colIndices[idx] == j) {
                values[idx] = value;
                return;
            }
        }
        // Add new element
        rowIndices.push_back(i);
        colIndices.push_back(j);
        values.push_back(value);
    }
    
    int get(int i, int j) {
        for (size_t idx = 0; idx < values.size(); idx++) {
            if (rowIndices[idx] == i && colIndices[idx] == j)
                return values[idx];
        }
        return 0;
    }
    
    int nnz() { return values.size(); }
    
    void display() {
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++)
                cout << get(i, j) << " ";
            cout << endl;
        }
    }
    
    void displaySparse() {
        cout << "Row: "; for (int r : rowIndices) cout << r << " "; cout << endl;
        cout << "Col: "; for (int c : colIndices) cout << c << " "; cout << endl;
        cout << "Val: "; for (int v : values) cout << v << " "; cout << endl;
    }
};

int main() {
    cout << "Sparse Matrix (COO Format):" << endl;
    SparseMatrixCOO sparse(5, 5);
    sparse.set(0, 0, 1);
    sparse.set(0, 4, 2);
    sparse.set(1, 1, 3);
    sparse.set(2, 2, 4);
    sparse.set(3, 0, 5);
    sparse.set(4, 3, 6);
    sparse.set(4, 4, 7);
    
    cout << "\nFull Matrix:" << endl;
    sparse.display();
    cout << "\nSparse Representation:" << endl;
    sparse.displaySparse();
    cout << "\nNon-zero elements: " << sparse.nnz() << endl;
    
    return 0;
}

import java.util.ArrayList;

public class SparseMatrixCOO {
    private int rows, cols;
    private ArrayList<Integer> rowIndices = new ArrayList<>();
    private ArrayList<Integer> colIndices = new ArrayList<>();
    private ArrayList<Integer> values = new ArrayList<>();
    
    public SparseMatrixCOO(int r, int c) {
        this.rows = r;
        this.cols = c;
    }
    
    public void set(int i, int j, int value) {
        if (value == 0) return;
        
        // Check if element exists
        for (int idx = 0; idx < values.size(); idx++) {
            if (rowIndices.get(idx) == i && colIndices.get(idx) == j) {
                values.set(idx, value);
                return;
            }
        }
        // Add new element
        rowIndices.add(i);
        colIndices.add(j);
        values.add(value);
    }
    
    public int get(int i, int j) {
        for (int idx = 0; idx < values.size(); idx++) {
            if (rowIndices.get(idx) == i && colIndices.get(idx) == j)
                return values.get(idx);
        }
        return 0;
    }
    
    public int nnz() { return values.size(); }
    
    public void display() {
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++)
                System.out.print(get(i, j) + " ");
            System.out.println();
        }
    }
    
    public void displaySparse() {
        System.out.println("Row: " + rowIndices);
        System.out.println("Col: " + colIndices);
        System.out.println("Val: " + values);
    }
    
    public static void main(String[] args) {
        System.out.println("Sparse Matrix (COO Format):");
        SparseMatrixCOO sparse = new SparseMatrixCOO(5, 5);
        sparse.set(0, 0, 1);
        sparse.set(0, 4, 2);
        sparse.set(1, 1, 3);
        sparse.set(2, 2, 4);
        sparse.set(3, 0, 5);
        sparse.set(4, 3, 6);
        sparse.set(4, 4, 7);
        
        System.out.println("\nFull Matrix:");
        sparse.display();
        System.out.println("\nSparse Representation:");
        sparse.displaySparse();
        System.out.println("\nNon-zero elements: " + sparse.nnz());
    }
}

Compressed Sparse Row (CSR) Format

CSR is the industry standard for sparse matrix storage in scientific computing. It uses three arrays: values (non-zero values in row order), col_indices (column of each value), and row_ptr (where each row starts in the values array). CSR gives \(O(\text{nnz}/n)\) average row access and efficient matrix-vector multiplication. SciPy, TensorFlow, and CUDA all use CSR as their primary sparse format. The tradeoff: column access is slow (\(O(\text{nnz})\)) — use CSC for that.

# Sparse Matrix - Compressed Sparse Row (CSR) Format
# Arrays:
#   - values: non-zero values (in row order)
#   - col_indices: column index of each value
#   - row_ptr: index in values where each row starts (length = rows + 1)
# Good for: row slicing, matrix-vector multiplication
# Bad for: column slicing, insertion

class SparseMatrixCSR:
    def __init__(self, rows, cols, row_ptr, col_indices, values):
        self.rows = rows
        self.cols = cols
        self.row_ptr = row_ptr      # Length: rows + 1
        self.col_indices = col_indices
        self.values = values
    
    @classmethod
    def from_dense(cls, matrix):
        """Create CSR from dense matrix"""
        rows = len(matrix)
        cols = len(matrix[0]) if rows > 0 else 0
        
        row_ptr = [0]
        col_indices = []
        values = []
        
        for i in range(rows):
            for j in range(cols):
                if matrix[i][j] != 0:
                    col_indices.append(j)
                    values.append(matrix[i][j])
            row_ptr.append(len(values))
        
        return cls(rows, cols, row_ptr, col_indices, values)
    
    def get(self, i, j):
        """Get element at (i, j) - O(log k) with binary search, O(k) linear"""
        start = self.row_ptr[i]
        end = self.row_ptr[i + 1]
        
        for idx in range(start, end):
            if self.col_indices[idx] == j:
                return self.values[idx]
        return 0
    
    def get_row(self, i):
        """Get all elements in row i - O(k) where k = elements in row"""
        start = self.row_ptr[i]
        end = self.row_ptr[i + 1]
        
        row = [0] * self.cols
        for idx in range(start, end):
            row[self.col_indices[idx]] = self.values[idx]
        return row
    
    def nnz(self):
        return len(self.values)
    
    def display(self):
        for i in range(self.rows):
            print(self.get_row(i))
    
    def display_csr(self):
        print(f"Values:      {self.values}")
        print(f"Col Indices: {self.col_indices}")
        print(f"Row Ptr:     {self.row_ptr}")
    
    def matrix_vector_mult(self, vector):
        """Multiply CSR matrix by vector - O(nnz)"""
        if len(vector) != self.cols:
            raise ValueError("Vector size must match matrix columns")
        
        result = [0] * self.rows
        for i in range(self.rows):
            start = self.row_ptr[i]
            end = self.row_ptr[i + 1]
            for idx in range(start, end):
                result[i] += self.values[idx] * vector[self.col_indices[idx]]
        return result

# Test CSR
dense = [
    [1, 0, 0, 2, 0],
    [0, 3, 0, 0, 0],
    [0, 0, 4, 0, 0],
    [5, 0, 0, 0, 0],
    [0, 0, 0, 6, 7]
]

print("CSR Sparse Matrix:")
csr = SparseMatrixCSR.from_dense(dense)
print("\nOriginal Matrix:")
csr.display()
print("\nCSR Representation:")
csr.display_csr()

# Matrix-vector multiplication
vec = [1, 2, 3, 4, 5]
result = csr.matrix_vector_mult(vec)
print(f"\nMatrix × {vec} = {result}")

#include <iostream>
#include <vector>
using namespace std;

class SparseMatrixCSR {
public:
    int rows, cols;
    vector<int> rowPtr, colIndices, values;
    
    SparseMatrixCSR(int r, int c, vector<int> rp, vector<int> ci, vector<int> v)
        : rows(r), cols(c), rowPtr(rp), colIndices(ci), values(v) {}
    
    static SparseMatrixCSR fromDense(vector<vector<int>>& matrix) {
        int rows = matrix.size();
        int cols = rows > 0 ? matrix[0].size() : 0;
        
        vector<int> rowPtr = {0};
        vector<int> colIndices, values;
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] != 0) {
                    colIndices.push_back(j);
                    values.push_back(matrix[i][j]);
                }
            }
            rowPtr.push_back(values.size());
        }
        return SparseMatrixCSR(rows, cols, rowPtr, colIndices, values);
    }
    
    int get(int i, int j) {
        for (int idx = rowPtr[i]; idx < rowPtr[i + 1]; idx++)
            if (colIndices[idx] == j) return values[idx];
        return 0;
    }
    
    vector<int> matVecMult(vector<int>& vec) {
        vector<int> result(rows, 0);
        for (int i = 0; i < rows; i++)
            for (int idx = rowPtr[i]; idx < rowPtr[i + 1]; idx++)
                result[i] += values[idx] * vec[colIndices[idx]];
        return result;
    }
    
    void displayCSR() {
        cout << "Values: "; for (int v : values) cout << v << " "; cout << endl;
        cout << "ColIdx: "; for (int c : colIndices) cout << c << " "; cout << endl;
        cout << "RowPtr: "; for (int r : rowPtr) cout << r << " "; cout << endl;
    }
};

int main() {
    vector<vector<int>> dense = {
        {1, 0, 0, 2, 0}, {0, 3, 0, 0, 0}, {0, 0, 4, 0, 0},
        {5, 0, 0, 0, 0}, {0, 0, 0, 6, 7}
    };
    
    cout << "CSR Sparse Matrix:" << endl;
    SparseMatrixCSR csr = SparseMatrixCSR::fromDense(dense);
    csr.displayCSR();
    
    vector<int> vec = {1, 2, 3, 4, 5};
    vector<int> result = csr.matVecMult(vec);
    cout << "\nMatrix × vec = ";
    for (int r : result) cout << r << " ";
    cout << endl;
    
    return 0;
}

import java.util.*;

public class SparseMatrixCSR {
    int rows, cols;
    int[] rowPtr, colIndices, values;
    
    public SparseMatrixCSR(int r, int c, int[] rp, int[] ci, int[] v) {
        rows = r; cols = c; rowPtr = rp; colIndices = ci; values = v;
    }
    
    public static SparseMatrixCSR fromDense(int[][] matrix) {
        int rows = matrix.length;
        int cols = rows > 0 ? matrix[0].length : 0;
        
        List<Integer> rpList = new ArrayList<>();
        List<Integer> ciList = new ArrayList<>();
        List<Integer> vList = new ArrayList<>();
        rpList.add(0);
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] != 0) {
                    ciList.add(j);
                    vList.add(matrix[i][j]);
                }
            }
            rpList.add(vList.size());
        }
        
        return new SparseMatrixCSR(rows, cols,
            rpList.stream().mapToInt(i -> i).toArray(),
            ciList.stream().mapToInt(i -> i).toArray(),
            vList.stream().mapToInt(i -> i).toArray());
    }
    
    public int[] matVecMult(int[] vec) {
        int[] result = new int[rows];
        for (int i = 0; i < rows; i++)
            for (int idx = rowPtr[i]; idx < rowPtr[i + 1]; idx++)
                result[i] += values[idx] * vec[colIndices[idx]];
        return result;
    }
    
    public void displayCSR() {
        System.out.println("Values: " + Arrays.toString(values));
        System.out.println("ColIdx: " + Arrays.toString(colIndices));
        System.out.println("RowPtr: " + Arrays.toString(rowPtr));
    }
    
    public static void main(String[] args) {
        int[][] dense = {
            {1, 0, 0, 2, 0}, {0, 3, 0, 0, 0}, {0, 0, 4, 0, 0},
            {5, 0, 0, 0, 0}, {0, 0, 0, 6, 7}
        };
        
        System.out.println("CSR Sparse Matrix:");
        SparseMatrixCSR csr = SparseMatrixCSR.fromDense(dense);
        csr.displayCSR();
        
        int[] vec = {1, 2, 3, 4, 5};
        int[] result = csr.matVecMult(vec);
        System.out.println("\nMatrix × vec = " + Arrays.toString(result));
    }
}

Compressed Sparse Column (CSC) Format

CSC is the column analog of CSR: values and row_indices are stored in column order, with a col_ptr array indicating where each column starts. CSC excels at column slicing and column-wise operations — making it ideal for solving sparse linear systems (\(Ax = b\)) where column access patterns dominate. MATLAB uses CSC internally for its sparse matrices. In practice, choose CSR for row-heavy operations and CSC for column-heavy ones; converting between them is \(O(\text{nnz})\).

# Sparse Matrix - Compressed Sparse Column (CSC) Format
# Arrays:
#   - values: non-zero values (in column order)
#   - row_indices: row index of each value
#   - col_ptr: index in values where each column starts
# Good for: column slicing, transposing CSR
# Bad for: row slicing

class SparseMatrixCSC:
    def __init__(self, rows, cols, col_ptr, row_indices, values):
        self.rows = rows
        self.cols = cols
        self.col_ptr = col_ptr
        self.row_indices = row_indices
        self.values = values
    
    @classmethod
    def from_dense(cls, matrix):
        """Create CSC from dense matrix"""
        rows = len(matrix)
        cols = len(matrix[0]) if rows > 0 else 0
        
        col_ptr = [0]
        row_indices = []
        values = []
        
        for j in range(cols):
            for i in range(rows):
                if matrix[i][j] != 0:
                    row_indices.append(i)
                    values.append(matrix[i][j])
            col_ptr.append(len(values))
        
        return cls(rows, cols, col_ptr, row_indices, values)
    
    def get(self, i, j):
        """Get element at (i, j)"""
        start = self.col_ptr[j]
        end = self.col_ptr[j + 1]
        
        for idx in range(start, end):
            if self.row_indices[idx] == i:
                return self.values[idx]
        return 0
    
    def get_col(self, j):
        """Get all elements in column j"""
        start = self.col_ptr[j]
        end = self.col_ptr[j + 1]
        
        col = [0] * self.rows
        for idx in range(start, end):
            col[self.row_indices[idx]] = self.values[idx]
        return col
    
    def display_csc(self):
        print(f"Values:      {self.values}")
        print(f"Row Indices: {self.row_indices}")
        print(f"Col Ptr:     {self.col_ptr}")

# Test CSC
dense = [
    [1, 0, 0, 2, 0],
    [0, 3, 0, 0, 0],
    [0, 0, 4, 0, 0],
    [5, 0, 0, 0, 0],
    [0, 0, 0, 6, 7]
]
print("CSC Sparse Matrix:")
csc = SparseMatrixCSC.from_dense(dense)
print("\nCSC Representation:")
csc.display_csc()
print(f"\nColumn 0: {csc.get_col(0)}")
print(f"Column 3: {csc.get_col(3)}")

#include <iostream>
#include <vector>
using namespace std;

class SparseMatrixCSC {
public:
    int rows, cols;
    vector<int> colPtr, rowIndices, values;
    
    SparseMatrixCSC(int r, int c, vector<int> cp, vector<int> ri, vector<int> v)
        : rows(r), cols(c), colPtr(cp), rowIndices(ri), values(v) {}
    
    static SparseMatrixCSC fromDense(vector<vector<int>>& matrix) {
        int rows = matrix.size();
        int cols = rows > 0 ? matrix[0].size() : 0;
        
        vector<int> colPtr = {0};
        vector<int> rowIndices, values;
        
        for (int j = 0; j < cols; j++) {
            for (int i = 0; i < rows; i++) {
                if (matrix[i][j] != 0) {
                    rowIndices.push_back(i);
                    values.push_back(matrix[i][j]);
                }
            }
            colPtr.push_back(values.size());
        }
        return SparseMatrixCSC(rows, cols, colPtr, rowIndices, values);
    }
    
    vector<int> getCol(int j) {
        vector<int> col(rows, 0);
        for (int idx = colPtr[j]; idx < colPtr[j + 1]; idx++)
            col[rowIndices[idx]] = values[idx];
        return col;
    }
    
    void displayCSC() {
        cout << "Values: "; for (int v : values) cout << v << " "; cout << endl;
        cout << "RowIdx: "; for (int r : rowIndices) cout << r << " "; cout << endl;
        cout << "ColPtr: "; for (int c : colPtr) cout << c << " "; cout << endl;
    }
};

int main() {
    vector<vector<int>> dense = {
        {1, 0, 0, 2, 0}, {0, 3, 0, 0, 0}, {0, 0, 4, 0, 0},
        {5, 0, 0, 0, 0}, {0, 0, 0, 6, 7}
    };
    
    cout << "CSC Sparse Matrix:" << endl;
    SparseMatrixCSC csc = SparseMatrixCSC::fromDense(dense);
    csc.displayCSC();
    
    cout << "\nColumn 0: ";
    for (int v : csc.getCol(0)) cout << v << " ";
    cout << "\nColumn 3: ";
    for (int v : csc.getCol(3)) cout << v << " ";
    cout << endl;
    
    return 0;
}

import java.util.*;

public class SparseMatrixCSC {
    int rows, cols;
    int[] colPtr, rowIndices, values;
    
    public SparseMatrixCSC(int r, int c, int[] cp, int[] ri, int[] v) {
        rows = r; cols = c; colPtr = cp; rowIndices = ri; values = v;
    }
    
    public static SparseMatrixCSC fromDense(int[][] matrix) {
        int rows = matrix.length;
        int cols = rows > 0 ? matrix[0].length : 0;
        
        List<Integer> cpList = new ArrayList<>();
        List<Integer> riList = new ArrayList<>();
        List<Integer> vList = new ArrayList<>();
        cpList.add(0);
        
        for (int j = 0; j < cols; j++) {
            for (int i = 0; i < rows; i++) {
                if (matrix[i][j] != 0) {
                    riList.add(i);
                    vList.add(matrix[i][j]);
                }
            }
            cpList.add(vList.size());
        }
        
        return new SparseMatrixCSC(rows, cols,
            cpList.stream().mapToInt(i -> i).toArray(),
            riList.stream().mapToInt(i -> i).toArray(),
            vList.stream().mapToInt(i -> i).toArray());
    }
    
    public int[] getCol(int j) {
        int[] col = new int[rows];
        for (int idx = colPtr[j]; idx < colPtr[j + 1]; idx++)
            col[rowIndices[idx]] = values[idx];
        return col;
    }
    
    public void displayCSC() {
        System.out.println("Values: " + Arrays.toString(values));
        System.out.println("RowIdx: " + Arrays.toString(rowIndices));
        System.out.println("ColPtr: " + Arrays.toString(colPtr));
    }
    
    public static void main(String[] args) {
        int[][] dense = {
            {1, 0, 0, 2, 0}, {0, 3, 0, 0, 0}, {0, 0, 4, 0, 0},
            {5, 0, 0, 0, 0}, {0, 0, 0, 6, 7}
        };
        
        System.out.println("CSC Sparse Matrix:");
        SparseMatrixCSC csc = SparseMatrixCSC.fromDense(dense);
        csc.displayCSC();
        
        System.out.println("\nColumn 0: " + Arrays.toString(csc.getCol(0)));
        System.out.println("Column 3: " + Arrays.toString(csc.getCol(3)));
    }
}

Sparse Format Comparison

Operation	COO	CSR	CSC
Construction	\(O(1)\) per element	O(nnz)	O(nnz)
Random Access	O(nnz)	O(log k)	O(log k)
Row Slice	O(nnz)	\(O(k)\)	O(nnz)
Column Slice	O(nnz)	O(nnz)	\(O(k)\)
Mat-Vec Mult	O(nnz)	O(nnz) ?	O(nnz)

k = number of non-zeros in the row/column

Polynomial Representation

Polynomials can be represented using arrays. For sparse polynomials (many zero coefficients), we store only non-zero terms.

# Polynomial Representation Using Arrays
# Dense: Store all coefficients from degree 0 to max_degree
# Sparse: Store only non-zero terms as (coefficient, exponent) pairs

class DensePolynomial:
    """Dense polynomial representation"""
    def __init__(self, coefficients):
        # coefficients[i] = coefficient of x^i
        self.coeffs = coefficients
    
    def degree(self):
        return len(self.coeffs) - 1
    
    def evaluate(self, x):
        """Evaluate polynomial at x using Horner's method - O(n)"""
        result = 0
        for coef in reversed(self.coeffs):
            result = result * x + coef
        return result
    
    def __add__(self, other):
        """Add two polynomials"""
        max_len = max(len(self.coeffs), len(other.coeffs))
        result = [0] * max_len
        for i in range(len(self.coeffs)):
            result[i] += self.coeffs[i]
        for i in range(len(other.coeffs)):
            result[i] += other.coeffs[i]
        return DensePolynomial(result)
    
    def __str__(self):
        terms = []
        for i, c in enumerate(self.coeffs):
            if c != 0:
                if i == 0:
                    terms.append(f"{c}")
                elif i == 1:
                    terms.append(f"{c}x")
                else:
                    terms.append(f"{c}x^{i}")
        return " + ".join(terms) if terms else "0"

# Test Dense Polynomial
# p(x) = 3 + 2x + 5x^2
p1 = DensePolynomial([3, 2, 5])
print(f"p1(x) = {p1}")
print(f"p1(2) = {p1.evaluate(2)}")  # 3 + 4 + 20 = 27

# q(x) = 1 + 4x^2
p2 = DensePolynomial([1, 0, 4])
print(f"p2(x) = {p2}")

# Addition
p3 = p1 + p2
print(f"p1 + p2 = {p3}")  # 4 + 2x + 9x^2

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

class DensePolynomial {
public:
    vector<int> coeffs;
    
    DensePolynomial(vector<int> c) : coeffs(c) {}
    
    int degree() { return coeffs.size() - 1; }
    
    // Evaluate using Horner's method - O(n)
    long long evaluate(int x) {
        long long result = 0;
        for (int i = coeffs.size() - 1; i >= 0; i--)
            result = result * x + coeffs[i];
        return result;
    }
    
    DensePolynomial add(DensePolynomial& other) {
        int maxLen = max(coeffs.size(), other.coeffs.size());
        vector<int> result(maxLen, 0);
        for (size_t i = 0; i < coeffs.size(); i++)
            result[i] += coeffs[i];
        for (size_t i = 0; i < other.coeffs.size(); i++)
            result[i] += other.coeffs[i];
        return DensePolynomial(result);
    }
    
    string toString() {
        string result;
        for (size_t i = 0; i < coeffs.size(); i++) {
            if (coeffs[i] != 0) {
                if (!result.empty()) result += " + ";
                if (i == 0) result += to_string(coeffs[i]);
                else if (i == 1) result += to_string(coeffs[i]) + "x";
                else result += to_string(coeffs[i]) + "x^" + to_string(i);
            }
        }
        return result.empty() ? "0" : result;
    }
};

int main() {
    // p(x) = 3 + 2x + 5x^2
    DensePolynomial p1({3, 2, 5});
    cout << "p1(x) = " << p1.toString() << endl;
    cout << "p1(2) = " << p1.evaluate(2) << endl;  // 27
    
    // q(x) = 1 + 4x^2
    DensePolynomial p2({1, 0, 4});
    cout << "p2(x) = " << p2.toString() << endl;
    
    // Addition
    DensePolynomial p3 = p1.add(p2);
    cout << "p1 + p2 = " << p3.toString() << endl;  // 4 + 2x + 9x^2
    
    return 0;
}

public class DensePolynomial {
    private int[] coeffs;
    
    public DensePolynomial(int[] c) { coeffs = c.clone(); }
    
    public int degree() { return coeffs.length - 1; }
    
    // Evaluate using Horner's method - O(n)
    public long evaluate(int x) {
        long result = 0;
        for (int i = coeffs.length - 1; i >= 0; i--)
            result = result * x + coeffs[i];
        return result;
    }
    
    public DensePolynomial add(DensePolynomial other) {
        int maxLen = Math.max(coeffs.length, other.coeffs.length);
        int[] result = new int[maxLen];
        for (int i = 0; i < coeffs.length; i++)
            result[i] += coeffs[i];
        for (int i = 0; i < other.coeffs.length; i++)
            result[i] += other.coeffs[i];
        return new DensePolynomial(result);
    }
    
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < coeffs.length; i++) {
            if (coeffs[i] != 0) {
                if (sb.length() > 0) sb.append(" + ");
                if (i == 0) sb.append(coeffs[i]);
                else if (i == 1) sb.append(coeffs[i] + "x");
                else sb.append(coeffs[i] + "x^" + i);
            }
        }
        return sb.length() == 0 ? "0" : sb.toString();
    }
    
    public static void main(String[] args) {
        // p(x) = 3 + 2x + 5x^2
        DensePolynomial p1 = new DensePolynomial(new int[]{3, 2, 5});
        System.out.println("p1(x) = " + p1);
        System.out.println("p1(2) = " + p1.evaluate(2));  // 27
        
        // q(x) = 1 + 4x^2
        DensePolynomial p2 = new DensePolynomial(new int[]{1, 0, 4});
        System.out.println("p2(x) = " + p2);
        
        // Addition
        DensePolynomial p3 = p1.add(p2);
        System.out.println("p1 + p2 = " + p3);  // 4 + 2x + 9x^2
    }
}

Sparse Polynomial and Operations

# Sparse Polynomial Representation
# Store only non-zero terms as (coefficient, exponent) pairs
# Efficient for polynomials like: 3 + 5x^100 + 2x^1000

class SparsePolynomial:
    def __init__(self, terms=None):
        # terms: list of (coefficient, exponent) tuples
        self.terms = {}  # exponent -> coefficient
        if terms:
            for coef, exp in terms:
                if coef != 0:
                    self.terms[exp] = self.terms.get(exp, 0) + coef
    
    def degree(self):
        return max(self.terms.keys()) if self.terms else 0
    
    def evaluate(self, x):
        """Evaluate polynomial at x - O(k) where k = non-zero terms"""
        result = 0
        for exp, coef in self.terms.items():
            result += coef * (x ** exp)
        return result
    
    def __add__(self, other):
        """Add two sparse polynomials - O(k1 + k2)"""
        result = SparsePolynomial()
        result.terms = self.terms.copy()
        for exp, coef in other.terms.items():
            result.terms[exp] = result.terms.get(exp, 0) + coef
            if result.terms[exp] == 0:
                del result.terms[exp]
        return result
    
    def __mul__(self, other):
        """Multiply two sparse polynomials - O(k1 * k2)"""
        result = SparsePolynomial()
        for exp1, coef1 in self.terms.items():
            for exp2, coef2 in other.terms.items():
                new_exp = exp1 + exp2
                new_coef = coef1 * coef2
                result.terms[new_exp] = result.terms.get(new_exp, 0) + new_coef
        return result
    
    def __str__(self):
        if not self.terms:
            return "0"
        sorted_terms = sorted(self.terms.items())
        parts = []
        for exp, coef in sorted_terms:
            if exp == 0:
                parts.append(f"{coef}")
            elif exp == 1:
                parts.append(f"{coef}x")
            else:
                parts.append(f"{coef}x^{exp}")
        return " + ".join(parts)

# Test Sparse Polynomial
# p(x) = 5 + 3x^10 + 2x^100
sp1 = SparsePolynomial([(5, 0), (3, 10), (2, 100)])
print(f"\nSparse p1(x) = {sp1}")
print(f"Degree: {sp1.degree()}")
print(f"p1(1) = {sp1.evaluate(1)}")  # 5 + 3 + 2 = 10

# q(x) = 1 + x^10
sp2 = SparsePolynomial([(1, 0), (1, 10)])
print(f"p2(x) = {sp2}")

# Addition
sp3 = sp1 + sp2
print(f"p1 + p2 = {sp3}")

# Multiplication
sp4 = SparsePolynomial([(2, 0), (3, 1)])  # 2 + 3x
sp5 = SparsePolynomial([(1, 0), (4, 1)])  # 1 + 4x
sp6 = sp4 * sp5
print(f"\n({sp4}) × ({sp5}) = {sp6}")  # 2 + 11x + 12x^2

# Space comparison
print(f"\nSpace for x^1000 polynomial:")
print(f"  Dense: 1001 coefficients")
print(f"  Sparse: 1 term (2 values)")

#include <iostream>
#include <map>
#include <cmath>
using namespace std;

class SparsePolynomial {
public:
    map<int, int> terms;  // exponent -> coefficient
    
    SparsePolynomial() {}
    
    void addTerm(int coef, int exp) {
        if (coef != 0) {
            terms[exp] += coef;
            if (terms[exp] == 0) terms.erase(exp);
        }
    }
    
    int degree() {
        return terms.empty() ? 0 : terms.rbegin()->first;
    }
    
    long long evaluate(int x) {
        long long result = 0;
        for (auto& [exp, coef] : terms)
            result += coef * (long long)pow(x, exp);
        return result;
    }
    
    SparsePolynomial add(SparsePolynomial& other) {
        SparsePolynomial result;
        result.terms = terms;
        for (auto& [exp, coef] : other.terms)
            result.addTerm(coef, exp);
        return result;
    }
    
    SparsePolynomial multiply(SparsePolynomial& other) {
        SparsePolynomial result;
        for (auto& [e1, c1] : terms)
            for (auto& [e2, c2] : other.terms)
                result.addTerm(c1 * c2, e1 + e2);
        return result;
    }
    
    void print() {
        bool first = true;
        for (auto& [exp, coef] : terms) {
            if (!first) cout << " + ";
            if (exp == 0) cout << coef;
            else if (exp == 1) cout << coef << "x";
            else cout << coef << "x^" << exp;
            first = false;
        }
        if (first) cout << "0";
        cout << endl;
    }
};

int main() {
    // p(x) = 5 + 3x^10 + 2x^100
    SparsePolynomial sp1;
    sp1.addTerm(5, 0); sp1.addTerm(3, 10); sp1.addTerm(2, 100);
    cout << "Sparse p1(x) = "; sp1.print();
    cout << "p1(1) = " << sp1.evaluate(1) << endl;  // 10
    
    // Multiplication: (2 + 3x) × (1 + 4x)
    SparsePolynomial sp4, sp5;
    sp4.addTerm(2, 0); sp4.addTerm(3, 1);
    sp5.addTerm(1, 0); sp5.addTerm(4, 1);
    SparsePolynomial sp6 = sp4.multiply(sp5);
    cout << "Product = "; sp6.print();  // 2 + 11x + 12x^2
    
    return 0;
}

import java.util.*;

public class SparsePolynomial {
    private TreeMap<Integer, Integer> terms = new TreeMap<>();
    
    public void addTerm(int coef, int exp) {
        if (coef != 0) {
            terms.merge(exp, coef, Integer::sum);
            if (terms.get(exp) == 0) terms.remove(exp);
        }
    }
    
    public int degree() {
        return terms.isEmpty() ? 0 : terms.lastKey();
    }
    
    public long evaluate(int x) {
        long result = 0;
        for (var entry : terms.entrySet())
            result += entry.getValue() * (long)Math.pow(x, entry.getKey());
        return result;
    }
    
    public SparsePolynomial add(SparsePolynomial other) {
        SparsePolynomial result = new SparsePolynomial();
        result.terms = new TreeMap<>(terms);
        for (var entry : other.terms.entrySet())
            result.addTerm(entry.getValue(), entry.getKey());
        return result;
    }
    
    public SparsePolynomial multiply(SparsePolynomial other) {
        SparsePolynomial result = new SparsePolynomial();
        for (var e1 : terms.entrySet())
            for (var e2 : other.terms.entrySet())
                result.addTerm(e1.getValue() * e2.getValue(), 
                              e1.getKey() + e2.getKey());
        return result;
    }
    
    public String toString() {
        if (terms.isEmpty()) return "0";
        StringBuilder sb = new StringBuilder();
        for (var entry : terms.entrySet()) {
            if (sb.length() > 0) sb.append(" + ");
            int exp = entry.getKey(), coef = entry.getValue();
            if (exp == 0) sb.append(coef);
            else if (exp == 1) sb.append(coef + "x");
            else sb.append(coef + "x^" + exp);
        }
        return sb.toString();
    }
    
    public static void main(String[] args) {
        // p(x) = 5 + 3x^10 + 2x^100
        SparsePolynomial sp1 = new SparsePolynomial();
        sp1.addTerm(5, 0); sp1.addTerm(3, 10); sp1.addTerm(2, 100);
        System.out.println("Sparse p1(x) = " + sp1);
        System.out.println("p1(1) = " + sp1.evaluate(1));  // 10
        
        // Multiplication: (2 + 3x) × (1 + 4x)
        SparsePolynomial sp4 = new SparsePolynomial();
        SparsePolynomial sp5 = new SparsePolynomial();
        sp4.addTerm(2, 0); sp4.addTerm(3, 1);
        sp5.addTerm(1, 0); sp5.addTerm(4, 1);
        System.out.println("Product = " + sp4.multiply(sp5));  // 2 + 11x + 12x^2
    }
}

LeetCode Practice Problems

Medium 54. Spiral Matrix

Given an m×n matrix, return all elements in spiral order.

# LeetCode 54 - Spiral Matrix
# Time: O(m×n), Space: O(1) excluding output

def spiralOrder(matrix):
    if not matrix:
        return []
    
    result = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    
    while top <= bottom and left <= right:
        # Traverse right
        for col in range(left, right + 1):
            result.append(matrix[top][col])
        top += 1
        
        # Traverse down
        for row in range(top, bottom + 1):
            result.append(matrix[row][right])
        right -= 1
        
        # Traverse left
        if top <= bottom:
            for col in range(right, left - 1, -1):
                result.append(matrix[bottom][col])
            bottom -= 1
        
        # Traverse up
        if left <= right:
            for row in range(bottom, top - 1, -1):
                result.append(matrix[row][left])
            left += 1
    
    return result

# Test
matrix = [[1,2,3],[4,5,6],[7,8,9]]
print(spiralOrder(matrix))  # [1,2,3,6,9,8,7,4,5]

// LeetCode 54 - Spiral Matrix
// Time: O(m×n), Space: O(1) excluding output
#include <vector>
using namespace std;

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector<int> result;
    if (matrix.empty()) return result;
    
    int top = 0, bottom = matrix.size() - 1;
    int left = 0, right = matrix[0].size() - 1;
    
    while (top <= bottom && left <= right) {
        // Traverse right
        for (int col = left; col <= right; col++)
            result.push_back(matrix[top][col]);
        top++;
        
        // Traverse down
        for (int row = top; row <= bottom; row++)
            result.push_back(matrix[row][right]);
        right--;
        
        // Traverse left
        if (top <= bottom) {
            for (int col = right; col >= left; col--)
                result.push_back(matrix[bottom][col]);
            bottom--;
        }
        
        // Traverse up
        if (left <= right) {
            for (int row = bottom; row >= top; row--)
                result.push_back(matrix[row][left]);
            left++;
        }
    }
    return result;
}

// LeetCode 54 - Spiral Matrix
// Time: O(m×n), Space: O(1) excluding output
import java.util.*;

public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> result = new ArrayList<>();
    if (matrix.length == 0) return result;
    
    int top = 0, bottom = matrix.length - 1;
    int left = 0, right = matrix[0].length - 1;
    
    while (top <= bottom && left <= right) {
        // Traverse right
        for (int col = left; col <= right; col++)
            result.add(matrix[top][col]);
        top++;
        
        // Traverse down
        for (int row = top; row <= bottom; row++)
            result.add(matrix[row][right]);
        right--;
        
        // Traverse left
        if (top <= bottom) {
            for (int col = right; col >= left; col--)
                result.add(matrix[bottom][col]);
            bottom--;
        }
        
        // Traverse up
        if (left <= right) {
            for (int row = bottom; row >= top; row--)
                result.add(matrix[row][left]);
            left++;
        }
    }
    return result;
}

Medium 48. Rotate Image

Rotate the image (n×n matrix) by 90 degrees clockwise in-place.

# LeetCode 48 - Rotate Image
# Time: O(n²), Space: O(1)

def rotate(matrix):
    n = len(matrix)
    
    # Step 1: Transpose (swap matrix[i][j] with matrix[j][i])
    for i in range(n):
        for j in range(i + 1, n):
            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()

# Test
matrix = [[1,2,3],[4,5,6],[7,8,9]]
print("Before:", matrix)
rotate(matrix)
print("After:", matrix)  # [[7,4,1],[8,5,2],[9,6,3]]

// LeetCode 48 - Rotate Image
// Time: O(n²), Space: O(1)
#include <vector>
#include <algorithm>
using namespace std;

void rotate(vector<vector<int>>& matrix) {
    int n = matrix.size();
    
    // Step 1: Transpose
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            swap(matrix[i][j], matrix[j][i]);
    
    // Step 2: Reverse each row
    for (int i = 0; i < n; i++)
        reverse(matrix[i].begin(), matrix[i].end());
}

// LeetCode 48 - Rotate Image
// Time: O(n²), Space: O(1)

public void rotate(int[][] matrix) {
    int n = matrix.length;
    
    // Step 1: Transpose
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
    
    // Step 2: Reverse each row
    for (int i = 0; i < n; i++) {
        int left = 0, right = n - 1;
        while (left < right) {
            int temp = matrix[i][left];
            matrix[i][left] = matrix[i][right];
            matrix[i][right] = temp;
            left++; right--;
        }
    }
}

Medium 73. Set Matrix Zeroes

If an element is 0, set its entire row and column to 0. Do it in-place.

# LeetCode 73 - Set Matrix Zeroes
# Time: O(m×n), Space: O(1)

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    first_row_zero = False
    first_col_zero = False
    
    # Check if first row/col have zeros
    for j in range(n):
        if matrix[0][j] == 0:
            first_row_zero = True
            break
    
    for i in range(m):
        if matrix[i][0] == 0:
            first_col_zero = True
            break
    
    # Use first row/col 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 zeros 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
    
    # Handle first row/col
    if first_row_zero:
        for j in range(n):
            matrix[0][j] = 0
    
    if first_col_zero:
        for i in range(m):
            matrix[i][0] = 0

# Test
matrix = [[1,1,1],[1,0,1],[1,1,1]]
setZeroes(matrix)
print(matrix)  # [[1,0,1],[0,0,0],[1,0,1]]

// LeetCode 73 - Set Matrix Zeroes
// Time: O(m×n), Space: O(1)

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        bool firstRowZero = false, firstColZero = false;
        
        // Check if first row has zeros
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                firstRowZero = true;
                break;
            }
        }
        
        // Check if first column has zeros
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                firstColZero = true;
                break;
            }
        }
        
        // Use first row/col as markers
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        
        // Set zeros based on markers
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        
        // Handle first row
        if (firstRowZero) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
        
        // Handle first column
        if (firstColZero) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
};

int main() {
    Solution sol;
    vector<vector<int>> matrix = {{1,1,1},{1,0,1},{1,1,1}};
    sol.setZeroes(matrix);
    
    for (auto& row : matrix) {
        for (int val : row) cout << val << " ";
        cout << endl;
    }
    // Output: 1 0 1 / 0 0 0 / 1 0 1
    return 0;
}

// LeetCode 73 - Set Matrix Zeroes
// Time: O(m×n), Space: O(1)

import java.util.Arrays;

public class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean firstRowZero = false, firstColZero = false;
        
        // Check if first row has zeros
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                firstRowZero = true;
                break;
            }
        }
        
        // Check if first column has zeros
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                firstColZero = true;
                break;
            }
        }
        
        // Use first row/col as markers
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        
        // Set zeros based on markers
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        
        // Handle first row
        if (firstRowZero) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
        
        // Handle first column
        if (firstColZero) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] matrix = {{1,1,1},{1,0,1},{1,1,1}};
        sol.setZeroes(matrix);
        
        for (int[] row : matrix) {
            System.out.println(Arrays.toString(row));
        }
        // Output: [1, 0, 1] / [0, 0, 0] / [1, 0, 1]
    }
}

Medium 311. Sparse Matrix Multiplication

Given two sparse matrices, return their multiplication result.

# LeetCode 311 - Sparse Matrix Multiplication
# Time: O(m×k×n) worst, better for sparse
# Space: O(m×n)

def multiply(mat1, mat2):
    m, k = len(mat1), len(mat1[0])
    n = len(mat2[0])
    
    # Result matrix
    result = [[0] * n for _ in range(m)]
    
    # Optimization: Skip zeros in mat1
    for i in range(m):
        for j in range(k):
            if mat1[i][j] != 0:  # Only process non-zero
                for l in range(n):
                    if mat2[j][l] != 0:  # Skip zeros in mat2
                        result[i][l] += mat1[i][j] * mat2[j][l]
    
    return result

# More efficient using sparse representation
def multiply_sparse(mat1, mat2):
    m, k = len(mat1), len(mat1[0])
    n = len(mat2[0])
    
    # Convert to sparse: row -> list of (col, val)
    sparse1 = [[] for _ in range(m)]
    for i in range(m):
        for j in range(k):
            if mat1[i][j] != 0:
                sparse1[i].append((j, mat1[i][j]))
    
    sparse2 = [[] for _ in range(k)]
    for j in range(k):
        for l in range(n):
            if mat2[j][l] != 0:
                sparse2[j].append((l, mat2[j][l]))
    
    result = [[0] * n for _ in range(m)]
    
    for i in range(m):
        for j, val1 in sparse1[i]:
            for l, val2 in sparse2[j]:
                result[i][l] += val1 * val2
    
    return result

# Test
mat1 = [[1,0,0],[-1,0,3]]
mat2 = [[7,0,0],[0,0,0],[0,0,1]]
print(multiply_sparse(mat1, mat2))  # [[7,0,0],[-7,0,3]]

// LeetCode 311 - Sparse Matrix Multiplication
// Time: O(m×k×n) worst, better for sparse
// Space: O(m×n)

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    // Basic approach with zero skipping
    vector<vector<int>> multiply(vector<vector<int>>& mat1, 
                                   vector<vector<int>>& mat2) {
        int m = mat1.size(), k = mat1[0].size();
        int n = mat2[0].size();
        
        vector<vector<int>> result(m, vector<int>(n, 0));
        
        // Skip zeros in mat1
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < k; j++) {
                if (mat1[i][j] != 0) {
                    for (int l = 0; l < n; l++) {
                        if (mat2[j][l] != 0) {
                            result[i][l] += mat1[i][j] * mat2[j][l];
                        }
                    }
                }
            }
        }
        return result;
    }
    
    // More efficient sparse representation
    vector<vector<int>> multiplySparse(vector<vector<int>>& mat1, 
                                         vector<vector<int>>& mat2) {
        int m = mat1.size(), k = mat1[0].size();
        int n = mat2[0].size();
        
        // Convert to sparse: row -> list of (col, val)
        vector<vector<pair<int, int>>> sparse1(m);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < k; j++) {
                if (mat1[i][j] != 0) {
                    sparse1[i].push_back({j, mat1[i][j]});
                }
            }
        }
        
        vector<vector<pair<int, int>>> sparse2(k);
        for (int j = 0; j < k; j++) {
            for (int l = 0; l < n; l++) {
                if (mat2[j][l] != 0) {
                    sparse2[j].push_back({l, mat2[j][l]});
                }
            }
        }
        
        vector<vector<int>> result(m, vector<int>(n, 0));
        
        for (int i = 0; i < m; i++) {
            for (auto& [j, val1] : sparse1[i]) {
                for (auto& [l, val2] : sparse2[j]) {
                    result[i][l] += val1 * val2;
                }
            }
        }
        return result;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> mat1 = {{1,0,0},{-1,0,3}};
    vector<vector<int>> mat2 = {{7,0,0},{0,0,0},{0,0,1}};
    
    auto result = sol.multiplySparse(mat1, mat2);
    
    for (auto& row : result) {
        for (int val : row) cout << val << " ";
        cout << endl;
    }
    // Output: 7 0 0 / -7 0 3
    return 0;
}

// LeetCode 311 - Sparse Matrix Multiplication
// Time: O(m×k×n) worst, better for sparse
// Space: O(m×n)

import java.util.*;

public class Solution {
    // Basic approach with zero skipping
    public int[][] multiply(int[][] mat1, int[][] mat2) {
        int m = mat1.length, k = mat1[0].length;
        int n = mat2[0].length;
        
        int[][] result = new int[m][n];
        
        // Skip zeros in mat1
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < k; j++) {
                if (mat1[i][j] != 0) {
                    for (int l = 0; l < n; l++) {
                        if (mat2[j][l] != 0) {
                            result[i][l] += mat1[i][j] * mat2[j][l];
                        }
                    }
                }
            }
        }
        return result;
    }
    
    // More efficient sparse representation
    public int[][] multiplySparse(int[][] mat1, int[][] mat2) {
        int m = mat1.length, k = mat1[0].length;
        int n = mat2[0].length;
        
        // Convert to sparse: row -> list of (col, val)
        List<List<int[]>> sparse1 = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            sparse1.add(new ArrayList<>());
            for (int j = 0; j < k; j++) {
                if (mat1[i][j] != 0) {
                    sparse1.get(i).add(new int[]{j, mat1[i][j]});
                }
            }
        }
        
        List<List<int[]>> sparse2 = new ArrayList<>();
        for (int j = 0; j < k; j++) {
            sparse2.add(new ArrayList<>());
            for (int l = 0; l < n; l++) {
                if (mat2[j][l] != 0) {
                    sparse2.get(j).add(new int[]{l, mat2[j][l]});
                }
            }
        }
        
        int[][] result = new int[m][n];
        
        for (int i = 0; i < m; i++) {
            for (int[] entry1 : sparse1.get(i)) {
                int j = entry1[0], val1 = entry1[1];
                for (int[] entry2 : sparse2.get(j)) {
                    int l = entry2[0], val2 = entry2[1];
                    result[i][l] += val1 * val2;
                }
            }
        }
        return result;
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] mat1 = {{1,0,0},{-1,0,3}};
        int[][] mat2 = {{7,0,0},{0,0,0},{0,0,1}};
        
        int[][] result = sol.multiplySparse(mat1, mat2);
        
        for (int[] row : result) {
            System.out.println(Arrays.toString(row));
        }
        // Output: [7, 0, 0] / [-7, 0, 3]
    }
}

Next in the Series

In Part 6: Linked Lists, we’ll move from contiguous memory to pointer-based structures with linked lists — singly, doubly, and circular variants plus the manipulation techniques interviewers love.

Complete DSA Series Part 5: Matrices - Special & Sparse

Table of Contents

FAANG Interview Prep

Foundations, Memory & Complexity

Recursion Complete Guide

Arrays & Array ADT

Strings

Matrices

Linked Lists

Stack

Queue

Trees

BST & Balanced Trees

Heaps, Sorting & Hashing

Graphs, DP, Greedy & Backtracking

Introduction to Matrices