Search⌘ K
AI Features
Home
Courses
Decode the Coding Interview in Swift: Real-World Examples

Sparse Matrix Multiplication

Explore how to multiply two sparse matrices by converting them into dictionaries that store only non-zero elements. Learn to implement an efficient algorithm that iterates through these dictionaries to compute the output matrix, optimizing both time and space complexity for better performance in coding interviews.

We'll cover the following...

Description

We have two sparse matrices, A and B.

“A sparse matrix is one in which most of the elements are zero.”

You need to multiply the two matrices and return the output matrix. You can assume that A’s column number is equal to B’s row number.

Constraints

The following are some constraints:

  • 1 <= A.length, B.length <= 100
  • 1 <= A[i].length, B[i].length <= 100
  • -100 <= A[i][j], B[i][j] <= 100

Let’s review this scenario using the example below:

Coding exercise

Swift
import Swift
func multiply(A: [[Int]], B: [[Int]]) -> [[Int]] {
    // Write your code here
    return []
}
Sparse matrix multiplication exercise

Solution

We have two sparse matrices, meaning most of the matrices’ elements are zero. We can represent the input matrices as dictionaries, and only save the non-zero elements and ...