What if we compress both matrix?


  • 0
    Z

    I compressed both matrix and do two-pointer operations based on the compressed array.

        public int[][] multiply(int[][] A, int[][] B) {
            List<Integer>[] compA = new List[A.length];
            for (int i = 0; i < A.length; i++) {
                for (int j = 0; j < A[0].length; j++) {
                    if (compA[i] == null) {
                        List<Integer> list = new ArrayList<>();
                        compA[i] = list;
                    }
                    if (A[i][j] != 0) {
                        compA[i].add(j);
                        compA[i].add(A[i][j]);
                    }
                }
            }
            List<Integer>[] compB = new List[B[0].length];
            for (int i = 0; i < B[0].length; i++) {
                for (int j = 0; j < B.length; j++) {
                    if (compB[i] == null) {
                        List<Integer> list = new ArrayList<>();
                        compB[i] = list;
                    }
                    if (B[j][i] != 0) {
                        compB[i].add(j);
                        compB[i].add(B[j][i]);
                    }
                }
            }
    
            int[][] result = new int[A.length][B[0].length];
            for (int i = 0; i < A.length; i++) {
                List<Integer> rowA = compA[i];
                for (int j = 0; j < B[0].length; j++) {
                    List<Integer> colB = compB[j];
                    for (int indexA = 0, indexB = 0; indexA < rowA.size() && indexB < colB.size();) {
                        if (rowA.get(indexA) == colB.get(indexB)) {
                            result[i][j] += rowA.get(indexA + 1) * colB.get(indexB + 1);
                            indexA += 2;
                            indexB += 2;
                        } else if (rowA.get(indexA) < colB.get(indexB)) {
                            indexA += 2;
                        }  else {
                            indexB += 2;
                        }
                    }
                }
            }
            return result;
        }
    

Log in to reply
 

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