Java solution using only one HashMap/List Array instead of two. (118 ms)


  • 0

    Key points:

    1. Only one matrix, let's say B, is needed to be turned into a sparse vector stored in an Array or HashMap.
    2. While looping through A matrix, the sparse vector can be used to reduce the amount of calculations.
        public class Solution {
            class Element {
                int i;
                int val;
                Element(int idx, int value) {
                    i=idx;
                    val=value;
                }
            }
            public int[][] multiply(int[][] A, int[][] B) {
                if (A==null || B==null || A.length==0 || B.length == 0) return new int[0][0];
                List[] vectorB = new List[B.length];
                int[][] ret = new int[A.length][B[0].length];
                for (int i=0; i< B.length; i++) {
                    for (int j=0; j< B[0].length; j++) {
                        if (B[i][j] != 0) {
                            List<Element> list = (List<Element>)vectorB[i] != null ? vectorB[i] : new ArrayList<Element>();
                            list.add( new Element( j, B[i][j]) );
                            vectorB[i] = list;
                        }
                    }
                }
                for (int i=0; i< A.length; i++) {
                    for (int j=0; j< A[0].length; j++) {
                        if ( ( A[i][j] != 0)  && (vectorB[j] != null) ) {
                            for (Element elmB: (List<Element>)vectorB[j] ) {
                                ret[i][elmB.i] += A[i][j]*elmB.val;
                            }
                        }
                    }
                }
                return ret;
            }
        }
    

Log in to reply
 

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