Easiest JAVA solution


  • 101

    UPDATE: Thanks to @stpeterh we have this 70ms concise solution:


    public class Solution {
        public int[][] multiply(int[][] A, int[][] B) {
            int m = A.length, n = A[0].length, nB = B[0].length;
            int[][] C = new int[m][nB];
    
            for(int i = 0; i < m; i++) {
                for(int k = 0; k < n; k++) {
                    if (A[i][k] != 0) {
                        for (int j = 0; j < nB; j++) {
                            if (B[k][j] != 0) C[i][j] += A[i][k] * B[k][j];
                        }
                    }
                }
            }
            return C;   
        }
    }
    

    The followings is the original 75ms solution:

    The idea is derived from a CMU lecture.

    A sparse matrix can be represented as a sequence of rows, each of which is a sequence of (column-number, value) pairs of the nonzero values in the row.

    So let's create a non-zero array for A, and do multiplication on B.

    Hope it helps!


    public int[][] multiply(int[][] A, int[][] B) {
        int m = A.length, n = A[0].length, nB = B[0].length;
        int[][] result = new int[m][nB];
    
        List[] indexA = new List[m];
        for(int i = 0; i < m; i++) {
            List<Integer> numsA = new ArrayList<>();
            for(int j = 0; j < n; j++) {
                if(A[i][j] != 0){
                    numsA.add(j); 
                    numsA.add(A[i][j]);
                }
            }
            indexA[i] = numsA;
        }
    
        for(int i = 0; i < m; i++) {
            List<Integer> numsA = indexA[i];
            for(int p = 0; p < numsA.size() - 1; p += 2) {
                int colA = numsA.get(p);
                int valA = numsA.get(p + 1);
                for(int j = 0; j < nB; j ++) {
                    int valB = B[colA][j];
                    result[i][j] += valA * valB;
                }
            }
        }
    
        return result;   
    }
    

  • 5
    S

    Thanks for providing this nice solution, @yavinci. I have a question about it. It seems like the CMU lecture solution is for sparse matrix multiplies dense vector. And I guess "another non-zero array on B" could be useful. The reason is that, for an element [k, j] in B, it would be detected for non-zero elements several times on the fly, depending on how many i's make elements [i, k] non-zero in A. However, your solution is faster than my Java solution with two HashMaps. I guess the reason could be the efficiency of primitive types in your solution.


  • 0

    Thanks for you suggestion! Will try to improve it based on ours.


  • 0
    S

    Moreover, I guess the set of test cases is not good enough right now. Your solution inspired me to detecting both on the fly: storing non-zero elements in A in a List of Lists and then detecting B and do multiplication is kind of like detecting both on the fly. I tried in python, such a direct detection solution could be fast:

    class Solution(object):
        def multiply(self, A, B):
            """
            :type A: List[List[int]]
            :type B: List[List[int]]
            :rtype: List[List[int]]
            """
            if A is None or B is None: return None
            m, n, l = len(A), len(A[0]), len(B[0])
            if len(B) != n:
                raise Exception("A's column number must be equal to B's row number.")
            C = [[0 for _ in range(l)] for _ in range(m)]
            for i, row in enumerate(A):
                for k, eleA in enumerate(row):
                    if eleA:
                        for j, eleB in enumerate(B[k]):
                            if eleB: C[i][j] += eleA * eleB
            return C
    

  • 0

    Thanks! Can you use code shortcut for your code? Command + K?


  • 0
    S

    Sorry for that. And thanks for teaching the way to edit it :-).


  • 10
    S

    And the corresponding Java solution takes ~70ms:

    public class Solution {
        public int[][] multiply(int[][] A, int[][] B) {
            int m = A.length, n = A[0].length, nB = B[0].length;
            int[][] C = new int[m][nB];
    
            for(int i = 0; i < m; i++) {
                for(int k = 0; k < n; k++) {
                    if (A[i][k] != 0){
                        for (int j = 0; j < nB; j++) {
                            if (B[k][j] != 0) C[i][j] += A[i][k] * B[k][j];
                        }
                    }
                }
            }
            return C;   
        }
    }

  • 0
    S

    I do think that probably the test set is not good enough right now. There are only 12 test cases.


  • 1

    Amazing solution! This is so short. Better than mine. But... why this is so similar to the default implementation of multiplication.


  • 0
    S

    Thanks for your encouragement. I probably will update my old post, after I try with only having a table for B. Now I think probably we can detect B in advance and then detect A on the fly to do multiplications and additions.


  • 0

    Thanks for sharing your solution. Will upvote yours once you posted.


  • 0

    Why are you so hard working at Thanksgiving? Happy Thanksgiving, by the way!


  • 0
    S

    Happy Thanksgiving, yavinci :-) I felt I worked so hard too. So I just watched The Martian. It is pretty good. Based on our discussion, I updated my solution. Thanks again for discussing with me.


  • 0

    Nice discussing with you too! It looks like you have 6 solutions, which again demonstrate how hardcore you are today. Mission: Impossible is really good too. You should take a look. Now you've learnt using command + K, even if you tagged a movie name.


  • 0
    S

    Yes, I have not watched the 2015 Mission: Impossible, and would like to watch it. I am looking forward to watch the Star Wars: The Force Awakens as well.


  • 0

    Yeah. Me too!


  • 1
    E

    Isn't this like a brute force solution?


  • 0
    J

    Thanks a lot for sharing, I have the same question as GWTW above, isn't this brute force? Can you help explain a bit?


  • 10
    L

    Great solution!
    based on your second idea from CMU lecture, c++ implementation, 32 ms.

     vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
        const int rowA = A.size(), rowB = B.size();
        const int colA = A[0].size(), colB = B[0].size();
        vector<vector<int>> res(rowA, vector<int>(colB, 0));
        vector<vector<pair<int, int>>> sparseA(rowA, vector<pair<int,int>>());
    
        for(int i = 0; i < rowA; i++)
           for(int j = 0; j < colA; j++) {
            if(A[i][j] != 0)  sparseA[i].emplace_back(j, A[i][j]);
         }
        for (int i = 0; i < rowA; ++i) 
         for (auto noZeros : sparseA[i]) 
          for (int j = 0; j < rowB; ++j) {
              if(B[noZeros.first][j] != 0) res[i][j] += noZeros.second * B[noZeros.first][j];
        }
        return res;
    }

  • 0

    @lchen77, very fast solution. Thanks for sharing!


Log in to reply
 

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