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

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

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;
}
}
}
}
}``````

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

• 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?

• 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).

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

}
};``````

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