Java solution


  • 0
    M
    public class Solution {
        public int[][] multiply(int[][] A, int[][] B) {
            int m = A.length, l = A[0].length, n = B[0].length;
            ArrayList<Cell>[] mapA = new ArrayList[m]; // row : cell list
            for(int i=0; i<m; i++){
                mapA[i] = new ArrayList<>();
                for(int j=0; j<l; j++){
                    if(A[i][j] != 0)
                        mapA[i].add(new Cell(A[i][j], i, j));
                }
            }
            ArrayList<Cell>[] mapB = new ArrayList[n]; // col : cell list
            for(int j=0; j<n; j++){
                mapB[j] = new ArrayList<>();
                for(int i=0; i<l; i++){
                    if(B[i][j] != 0)
                        mapB[j].add(new Cell(B[i][j], i, j));
                }
            }
            int[][] res = new int[m][n];
            for(int i=0; i<m; i++){
                for(int j=0; j<n; j++){
                    int s=0, t=0;
                    while(s<mapA[i].size() && t<mapB[j].size()){
                        Cell cellA = mapA[i].get(s);
                        Cell cellB = mapB[j].get(t);
                        if(cellA.col<cellB.row){
                            s++;
                        } else if(cellA.col>cellB.row){
                            t++;
                        } else { //cellA.col==cellB.row
                            res[i][j] += cellA.val*cellB.val;
                            t++;
                            s++;
                        }
                    }
                }
            }
            return res;
        }
        
        class Cell{
            int val;
            int row, col;
            Cell(int val, int row, int col){
                this.val = val;
                this.row = row;
                this.col = col;
            }
        }
    }
    

Log in to reply
 

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