[Math] add a solution to Sparse Matrix Multiplication

soapyigu · soapyigu · commit 1e52f3802298 · 2020-01-19T18:31:30.000-08:00
diff --git a/Math/SparseMatrixMultiplication.swift b/Math/SparseMatrixMultiplication.swift
@@ -0,0 +1,37 @@
+/**
+ * Question Link: https://leetcode.com/problems/sparse-matrix-multiplication/
+ * Primary idea: Use a matrix to mark indices of an matrix where is not zero to optimize the multiplication
+ *
+ * Time Complexity: O(n^3), Space Complexity: O(n^2)
+ */
+
+class SparseMatrixMultiplication {
+    func multiply(_ A: [[Int]], _ B: [[Int]]) -> [[Int]] {
+        let l = A.count, m = B.count, n = B[0].count
+        
+        var res = Array(repeating: Array(repeating: 0, count: n), count: l)
+        
+        var nonZeroB = Array(repeating: [Int](), count: m)
+        for i in 0..<m {
+            for j in 0..<n {
+                if B[i][j] != 0 {
+                    nonZeroB[i].append(j)
+                }
+            }
+        }
+        
+        for i in 0..<l {
+            for j in 0..<m {
+                if A[i][j] == 0 {
+                    continue
+                }
+                
+                for k in nonZeroB[j] {
+                    res[i][k] += A[i][j] * B[j][k]
+                }
+            }
+        }
+        
+        return res
+    }
+}
diff --git a/README.md b/README.md
@@ -4,7 +4,7 @@
 ![Leetcode](./logo.png?style=centerme)
 
 ## Progress
-[Problem Status](#problem-status) shows the latest progress to all 1000+ questions. Currently we have 318 completed solutions. Note: questions with &hearts; mark means that you have to **Subscript to premium membership** of LeetCode to unlock them.
+[Problem Status](#problem-status) shows the latest progress to all 1000+ questions. Currently we have 319 completed solutions. Note: questions with &hearts; mark means that you have to **Subscript to premium membership** of LeetCode to unlock them.
 
 ## Contributors
 
@@ -332,6 +332,7 @@
 [Integer to Roman](https://leetcode.com/problems/integer-to-roman/)| [Swift](./Math/IntegerToRoman.swift)| Medium| O(n)| O(1)|
 [Roman to Integer](https://leetcode.com/problems/roman-to-integer/)| [Swift](./Math/RomanToInteger.swift)| Easy| O(n)| O(n)|
 [Integer to English Words](https://leetcode.com/problems/integer-to-english-words/)| [Swift](./Math/IntegerEnglishWords.swift)| Hard| O(n)| O(1)|
+[Sparse Matrix Multiplication](https://leetcode.com/problems/sparse-matrix-multiplication/)| [Swift](./Math/SparseMatrixMultiplication.swift)| Medium| O(n^3)| O(n^2)|
 [Rectangle Area](https://leetcode.com/problems/rectangle-area/)| [Swift](./Math/RectangleArea.swift)| Easy| O(1)| O(1)|
 [Minimum Moves to Equal Array Elements](https://leetcode.com/problems/minimum-moves-to-equal-array-elements/)| [Swift](./Math/MinimumMovesEqualArrayElements.swift)| Easy| O(n)| O(1)|
 [Trapping Rain Water](https://leetcode.com/problems/trapping-rain-water/)| [Swift](./Math/TrappingRainWater.swift)| Hard| O(n)| O(n)|
@@ -602,7 +603,7 @@
 |	[Swift](./Tree/BinaryTreeVerticalOrderTraversal.swift)	|	314	|	[Binary Tree Vertical Order Traversal](https://leetcode.com/problems/binary-tree-vertical-order-traversal/) &hearts;	|	Medium
 |	[Swift](./Math/SuperUglyNumber.swift)	|	313	|	[Super Ugly Number](https://leetcode.com/problems/super-ugly-number/)	|	Medium
 |	[Swift](./DP/GuessNumberHigherOrLowerII.swift)	|	312	|	[Burst Balloons](https://leetcode.com/problems/burst-balloons/)	|	Hard
-|		|	311	|	[Sparse Matrix Multiplication](https://leetcode.com/problems/sparse-matrix-multiplication/)  &hearts;	|	Medium
+|	[Swift](./Math/SparseMatrixMultiplication.swift)	|	311	|	[Sparse Matrix Multiplication](https://leetcode.com/problems/sparse-matrix-multiplication/)  &hearts;	|	Medium
 |		|	310	|	[Minimum Height Trees](https://leetcode.com/problems/minimum-height-trees/)	|	Medium
 |	[Swift](./DP/BestTimeBuySellStockCooldown.swift)	|	309	|	[Best Time to Buy and Sell Stock with Cooldown](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/)	|	Medium
 |		|	308	|	[Range Sum Query 2D - Mutable](https://leetcode.com/problems/range-sum-query-2d-mutable/) &hearts;	|	Hard
