LeetCode 311: Sparse Matrix Multiplication Solution

Master LeetCode problem 311 (Sparse Matrix Multiplication), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

311. Sparse Matrix Multiplication

Medium

Array Hash Table Matrix

Problem Explanation

Explanation:

To perform matrix multiplication for sparse matrices, we can optimize the process by only computing and storing the non-zero elements. The algorithm involves iterating through the non-zero elements of the first matrix and multiplying them with the corresponding elements in the second matrix to compute the result matrix.

Iterate through the non-zero elements of the first matrix, and for each non-zero element A[i][j], iterate through the corresponding row in the second matrix B[j][k].
Multiply A[i][j] with B[j][k] and add the result to the corresponding element in the result matrix C[i][k].
Repeat this process for all non-zero elements in the first matrix.
The resulting matrix C will be the product of the two sparse matrices.

Time complexity:

Let n be the number of rows in the first matrix, m be the number of columns in the first matrix, and p be the number of columns in the second matrix.
The time complexity of this algorithm is O(n * m * p), as we iterate through the non-zero elements of the matrices.

Space complexity:

We only store the non-zero elements and their positions in the result matrix, so the space complexity is O(n * p).

Solution Code

class Solution {
    public int[][] multiply(int[][] A, int[][] B) {
        int n = A.length;
        int m = A[0].length;
        int p = B[0].length;
        
        int[][] C = new int[n][p];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (A[i][j] != 0) {
                    for (int k = 0; k < p; k++) {
                        if (B[j][k] != 0) {
                            C[i][k] += A[i][j] * B[j][k];
                        }
                    }
                }
            }
        }
        
        return C;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 311 (Sparse Matrix Multiplication)?

This page provides optimized solutions for LeetCode problem 311 (Sparse Matrix Multiplication) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 311 (Sparse Matrix Multiplication)?

The time complexity for LeetCode 311 (Sparse Matrix Multiplication) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 311 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 311 in Java, C++, or Python.

Back to LeetCode Solutions