Java solution


  • 1
    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;
            }
        }
    }
    

  • 0
    D

    I think you're solution is good for a Data Structure Design solution. I really dislike solutions that have crappy variable names and modularisation.
    Redone your solution:

    
    public class Solution {
    
        public int[][] multiply(int[][] A, int[][] B) {
    
            List<Cell>[] mapA = convertToLILRow(A);
            List<Cell>[] mapB = convertToLILColumn(B);
    
            int aRows = A.length;
            int bColumns = B[0].length;
            int[][] result = new int[aRows][bColumns];
            multiplyLIL(result,mapA,mapB);
    
            return result;
        }
        private void multiplyLIL(int[][] result,List<Cell>[] mapA,List<Cell>[] mapB){
    
            for(int row=0; row<result.length; row++){
                for(int column=0; column<result[0].length; column++){
                    int aColumns=0;
                    int bRows=0;
                    while(aColumns<mapA[row].size() && bRows<mapB[column].size()){
                        Cell cellA = mapA[row].get(aColumns);
                        Cell cellB = mapB[column].get(bRows);
                        if(cellA.col<cellB.row){
                            aColumns++;
                        } else if(cellA.col>cellB.row){
                            bRows++;
                        } else { //cellA.col==cellB.row
                            result[row][column] += cellA.val*cellB.val;
                            bRows++;
                            aColumns++;
                        }
                    }
                }
            }
        }
        private List<Cell>[] convertToLILRow(int[][] matrix){
            int rows = matrix.length, columns = matrix[0].length;
            List<Cell>[] mapA = new ArrayList[rows]; // row : cell list
    
            for(int row=0; row < rows; row++){
                mapA[row] = new ArrayList<>();
                for(int column=0; column < columns; column++){
                    int cell = matrix[row][column];
                    if(cell != 0)
                        mapA[row].add(new Cell(cell, row, column));
                }
            }
            return mapA;
        }
        private List<Cell>[] convertToLILColumn(int[][] matrix){
            int rows = matrix.length, columns = matrix[0].length;
            List<Cell>[] mapB = new ArrayList[columns];
    
            for(int column = 0;column < columns;column++){
                mapB[column] = new ArrayList<>();
                for(int row = 0;row < rows;row++){
                    int cell = matrix[row][column];
                    if(cell != 0){
                        mapB[column].add(new Cell(cell,row,column));
                    }
                }
            }
            return mapB;
        }
    
    
        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.