Sparse Matrix Multiplication

Problem

Given two sparse matrices A and B, return the result of AB.

You may assume that A's column number is equal to B's row number.

Example:

A = [
  [ 1, 0, 0],
  [-1, 0, 3]
]

B = [
  [ 7, 0, 0 ],
  [ 0, 0, 0 ],
  [ 0, 0, 1 ]
]


     |  1 0 0 |   | 7 0 0 |   |  7 0 0 |
AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 |
                  | 0 0 1 |

Solution

public class Solution {
    public int[][] multiply(int[][] A, int[][] B) {
        int row = A.length, n = A[0].length, col = B[0].length;
        int[][] res = new int[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < col; k++) {
                    res[i][k] += A[i][j] * B[j][k];
                }
            }
        }
        return res;
    }
}

Analysis

Using the formula that res[i][k] = A[i][j] * B[j][k]
For each space in res, we need to get multiplication of all row from A and all col from B
Hence we use three nested for loops to make sure they cover all computations

results matching ""

    No results matching ""