Matrix Multiplication

We learn matrix multiplication in school, but it is much simpler with the help of programming.
Basically two matrices A[n][k] and B[k][m] can be multiplied in time O(n*k*m). Exemplified by this LC problem: https://leetcode.com/problems/sparse-matrix-multiplication/

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:
Input:

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

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

Output:

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

The solution is given down below, literally just following the rules of matrices multiplication. Cheers, ACC.

public class Solution
{
    public int[][] Multiply(int[][] A, int[][] B)
    {
        int[][] result = new int[A.Length][];

        for (int i = 0; i < result.Length; i++)
        {
            result[i] = new int[B[0].Length];
        }

        for (int r = 0; r < result.Length; r++)
        {
            for (int c = 0; c < result[0].Length; c++)
            {
                result[r][c] = 0;
                for (int i = 0; i < A[0].Length; i++)
                {
                    result[r][c] += (A[r][i] * B[i][c]);
                }
            }
        }

        return result;
    }
}

Comments

Popular posts from this blog

Count Binary Substrings

Count Vowels Permutation: Standard DP

Maximum Number of Balloons