Complete DSA Series Part 5: Matrices - Special & Sparse

Introduction to Matrices

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.

2D Array Representation

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

Python

# 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}")

C++

#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;
}

Java

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

Diagonal Matrix

A diagonal matrix has non-zero elements only on the main diagonal (where i = j). Instead of storing n² elements, we only need n elements.

Python

# 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%)

C++

#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;
}

Java

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 or below the diagonal. They require n(n+1)/2 elements instead of n².

Python

# 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()

C++

#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;
}

Java

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.

Python

# 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)}")

C++

#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;
}

Java

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.

Python

# 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()}")

C++

#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;
}

Java

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();
    }
}

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.

Coordinate Format (COO)

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

Python

# 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}%")

C++

#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;
}

Java

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 efficient for row-wise operations and matrix-vector multiplication. It stores values, column indices, and row pointers.

Python

# 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}")

C++

#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;
}

Java

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 efficient for column-wise operations. It's the column analog of CSR.

Python

# 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)}")

C++

#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;
}

Java

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)));
    }
}

Polynomial Representation

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

Python

# 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

C++

#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;
}

Java

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

Python

# 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)")

C++

#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;
}

Java

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

# 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;
}

# 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--;
        }
    }
}

# 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]
    }
}

# 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]
    }
}