I use two ArrayList to remember the row and column indices with 0, is this a constant space?


  • 0
    Q

    In Java the ArrayList can expand its size on demand, so I use two ArrayList to remember the row and column indices with 0. The space depends on how many 0s are in the matrix but should be less than m+n.

    Is it considered as a constant space?

    public class Solution {
    public void setZeroes(int[][] matrix) {
        ArrayList<Integer> rows = new ArrayList<>(); // row indices with 0
        ArrayList<Integer> columns = new ArrayList<>(); // column indices with 0
        
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    if (!rows.contains(i)) rows.add(i); // do not add duplicate
                    if (!columns.contains(j)) columns.add(j);
                }
            }
        }
        
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (rows.contains(i) || columns.contains(j)) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
    }

  • 3
    J

    Unfortunately no. O(m+n) is not O(1). It increase as m and n increase


  • 0
    Q

    The number of zeros may or may not increase as m/n increases.
    It's like O(k+l) where k and l is the number of 0s in rows and columns.
    How to calculate such space complexity?


  • 0
    J

    Big-O notation is used to describe 'limit'. As long as it MAY increase in the same 'level' of speed as m/n, it is O(n+m). Only when it's always constant, we say it's O(1).


  • 0
    L

    You can further decrease the space used by half.

    Instead of saving the row and column information of each cypher in two different arrays, you can save it in one array in the form (i*n+j) where matrix[i][j]=0 and matrix is of mxn order.

    My code for the same :

    class Solution {
    public:
        void setZeroes(vector<vector<int> > &matrix) {
            vector<int>mp;
            int m=matrix.size();
            int n=(m>0)?matrix[0].size():0;
            
            if(m==0 || n==0)
              return ;
              
            for(int i=0 ; i< m ;i++)
             for(int j=0 ; j<n ; j++)  
               if(matrix[i][j]==0)
                 mp.push_back(i*n+j);
                 
             for(int i=0 ; i<mp.size() ; i++)
              {
                  int r=mp[i]/n;
                  int c=mp[i]%n;
                  for(int j=0 ; j<n ;j++)
                    matrix[r][j]=0;
                    
                  for(int j=0 ; j<m ; j++)
                    matrix[j][c]=0;
              }
            
        }
    };

Log in to reply
 

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