C#: Easy to understand two solutions with explanation. (Accepted)


  • 0

    0_1523304248112_c8b17073-5aaf-4725-b510-e6ec828121e8-image.png
    Solution 1: Brute Force (TLE)

    public class Solution {
        public int[,] Multiply(int[,] A, int[,] B) {
            int resultRowCount = A.GetLength(0);
            int resultColCount = B.GetLength(1);
            int n = A.GetLength(1);  //A.GetLength(1) == B.GetLength(0)
            int[,] result = new int[resultRowCount, resultColCount];
            for (int i = 0; i < resultRowCount; i++)
                for (int j = 0; j < resultColCount; j++)                   
                    for (int k = 0; k < n; k++)
                        result[i, j] += A[i, k] * B[k, j];
            return result;        
        }
    }
    

    Solution 2: Using sparse representation of a matrix. (Accepted).
    Refer this to understand the sparse matrix representation.

    public struct ColumnAndValue {
        public int Column;
        public int Value;
        public ColumnAndValue(int column, int value) { 
            this.Column = column;
            this.Value = value;
        }
    }   
    
    public class Solution {
        public int[,] Multiply(int[,] A, int[,] B) {
            int resultRowCount = A.GetLength(0);      
            int resultColCount = B.GetLength(1);    
            int[,] result = new int[resultRowCount, resultColCount];
            int n = A.GetLength(1);     //A.GetLength(1) == B.GetLength(0)
            //Convert A to sparse representation.
            List<ColumnAndValue>[] sparseA = new List<ColumnAndValue>[resultRowCount];   //resultRowCount = A.GetLength(0)
            for (int i = 0; i < resultRowCount; i++) {
                List<ColumnAndValue> columnAndValueList = new List<ColumnAndValue>();
                for (int j = 0; j < n; j++)
                    if (A[i, j] != 0)
                        columnAndValueList.Add(new ColumnAndValue(j, A[i, j]));
                sparseA[i] = columnAndValueList;
            }
            //Multiply Sparse A with B
            for (int r = 0; r < sparseA.Length; r++) {      //sparseA == resultRowCount
                List<ColumnAndValue> numsA = sparseA[r];
                for (int cv = 0; cv < numsA.Count; cv++) {
                    int colA = numsA[cv].Column;
                    int valA = numsA[cv].Value;
                    for (int c = 0; c < resultColCount; c++) {   //resultColCount = B.GetLength(1)                    
                        int valB = B[colA, c];
                        if (valB != 0)
                            result[r, c] += valA * valB;
                    }
                }
            }
            return result;
        }
    }
    

    image


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.