Sparse Matrix Multiplication - Practice Coding Problems

Sparse Matrix Multiplication - Problem

Given two sparse matrices mat1 of size m x k and mat2 of size k x n, return the result of mat1 x mat2.

You may assume that multiplication is always possible.

A sparse matrix is a matrix in which most of the elements are zero. The key insight is to avoid unnecessary multiplications with zero values to optimize performance.

Input & Output

Example 1 — Basic Sparse Matrix

$ Input: mat1 = [[1,0,0],[-1,0,3]], mat2 = [[7,0,0],[0,0,0],[0,0,1]]

› Output: [[7,0,0],[-7,0,3]]

💡 Note: Row 0: 1×7 + 0×0 + 0×0 = 7, 1×0 + 0×0 + 0×0 = 0, 1×0 + 0×0 + 0×1 = 0. Row 1: -1×7 + 0×0 + 3×0 = -7, -1×0 + 0×0 + 3×0 = 0, -1×0 + 0×0 + 3×1 = 3

Example 2 — Dense Matrix

$ Input: mat1 = [[1,0]], mat2 = [[7],[0]]

› Output: [[7]]

💡 Note: Single element multiplication: 1×7 + 0×0 = 7

Example 3 — All Zeros Result

$ Input: mat1 = [[0,1],[0,0]], mat2 = [[1,0],[0,0]]

› Output: [[0,0],[0,0]]

💡 Note: Row 0: 0×1 + 1×0 = 0, 0×0 + 1×0 = 0. Row 1: 0×1 + 0×0 = 0, 0×0 + 0×0 = 0

Constraints

m == mat1.length
k == mat1[i].length == mat2.length
n == mat2[i].length
1 ≤ m, n, k ≤ 100
-100 ≤ mat1[i][j], mat2[i][j] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

Two sparse matrices with many zero elements

Process

Standard matrix multiplication but skip zero multiplications

Output

Resulting matrix from mat1 × mat2

Key Takeaway

🎯 Key Insight: Only multiply non-zero elements to achieve significant speedup for sparse matrices

Asked in

F Facebook 15 G Google 12 Li LinkedIn 8 M Microsoft 6

The key insight is to avoid multiplying by zero elements in sparse matrices. The optimized approach checks for zero values before performing multiplications, while the hash map approach stores only non-zero elements for maximum efficiency. Best approach depends on sparsity: simple optimization for moderately sparse, hash maps for extremely sparse. Time: O(m × n × k), Space: O(m × n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Matrix Multiplication	O(m × n × k)	O(m × n)	Standard matrix multiplication checking all elements
Hash Map for Sparse Representation	O(A × B × n)	O(A + B + C)	Store only non-zero elements using hash maps
Skip Zero Elements	O(m × n × k)	O(m × n)	Skip multiplications when first matrix element is zero

Brute Force Matrix Multiplication — Algorithm Steps

Create result matrix of size m x n
For each position (i,j), calculate dot product of row i and column j
Sum all products mat1[i][k] * mat2[k][j]

Visualization

Tap to expand

Step-by-Step Walkthrough

Setup

Initialize result matrix and iterate positions

Calculate

For each (i,j), compute dot product including zeros

Result

Final matrix with all computed values

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int** solution(int** mat1, int mat1Size, int* mat1ColSize, int** mat2, int mat2Size, int* mat2ColSize, int* returnSize, int** returnColumnSizes) {
    int m = mat1Size, k = mat1ColSize[0];
    int n = mat2ColSize[0];
    
    int** result = (int**)malloc(m * sizeof(int*));
    *returnColumnSizes = (int*)malloc(m * sizeof(int));
    *returnSize = m;
    
    for (int i = 0; i < m; i++) {
        result[i] = (int*)calloc(n, sizeof(int));
        (*returnColumnSizes)[i] = n;
        
        for (int j = 0; j < n; j++) {
            for (int p = 0; p < k; p++) {
                result[i][j] += mat1[i][p] * mat2[p][j];
            }
        }
    }
    
    return result;
}

int main() {
    // Simplified for demonstration
    printf("[[7,0,0],[-7,0,3]]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m × n × k)

Triple nested loops: m rows × n columns × k dot product calculations

✓ Linear Growth

Space Complexity

O(m × n)

Result matrix stores m × n elements

⚡ Linearithmic Space

89.5K Views

Medium Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Matrix Multiplication — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler