Replacing zeros (or NANs) in a matrix with the previous element row-wise or column-wise in a fully vectorized way

Question

I need to replace the zeros (or NaNs) in a matrix with the previous element row-wise, so basically I need this Matrix X

[0,1,2,2,1,0;  
5,6,3,0,0,2;  
0,0,1,1,0,1]  

To become like this:

[0,1,2,2,1,1;  
5,6,3,3,3,2;  
0,0,1,1,1,1],  

please note that if the first row element is zero it will stay like that.

I know that this has been solved for a single row or column vector in a vectorized way and this is one of the nicest way of doing that:

id = find(X);         
X(id(2:end)) = diff(X(id));       
Y = cumsum(X)  

The problem is that the indexing of a matrix in Matlab/Octave is consecutive and increments columnwise so it works for a single row or column but the same exact concept cannot be applied but needs to be modified with multiple rows 'cause each of raw/column starts fresh and must be regarded as independent. I've tried my best and googled the whole google but coukldn’t find a way out. If I apply that same very idea in a loop it gets too slow cause my matrices contain 3000 rows at least. Can anyone help me out of this please?

Answer 1

Modified version of Eitan's answer to avoid propagating values across rows:

Y = X'; %'
tf = Y > 0;
tf(1,:) = true;
idx = find(tf);
Y(idx(2:end)) = diff(Y(idx));
Y = reshape(cumsum(Y(:)),fliplr(size(X)))';

Answer 2

Special case when zeros are isolated in each row

You can do it using the two-output version of find to locate the zeros and NaN's in all columns except the first, and then using linear indexing to fill those entries with their row-wise preceding values:

[ii jj] = find( (X(:,2:end)==0) | isnan(X(:,2:end)) );
X(ii+jj*size(X,1)) = X(ii+(jj-1)*size(X,1));

General case (consecutive zeros are allowed on each row)

X(isnan(X)) = 0; %// handle NaN's and zeros in a unified way
aux = repmat(2.^(1:size(X,2)), size(X,1), 1) .* ...
    [ones(size(X,1),1) logical(X(:,2:end))]; %// positive powers of 2 or 0
col = floor(log2(cumsum(aux,2))); %// col index
ind = bsxfun(@plus, (col-1)*size(X,1), (1:size(X,1)).'); %'// linear index
Y = X(ind);

The trick is to make use of the matrix aux, which contains 0 if the corresponding entry of X is 0 and its column number is greater than 1; or else contains 2 raised to the column number. Thus, applying cumsum row-wise to this matrix, taking log2 and rounding down (matrix col) gives the column index of the rightmost nonzero entry up to the current entry, for each row (so this is a kind of row-wise "cummulative max" function.) It only remains to convert from column number to linear index (with bsxfun; could also be done with sub2ind) and use that to index X.

This is valid for moderate sizes of X only. For large sizes, the powers of 2 used by the code quickly approach realmax and incorrect indices result.

Example:

X =
     0     1     2     2     1     0     0
     5     6     3     0     0     2     3
     1     1     1     1     0     1     1

gives

>> Y
Y =
     0     1     2     2     1     1     1
     5     6     3     3     3     2     3
     1     1     1     1     1     1     1

Answer 3

You can generalize your own solution as follows:

Y = X.';                                       %'// Make a transposed copy of X
Y(isnan(Y)) = 0;
idx = find([ones(1, size(X, 1)); Y(2:end, :)]);
Y(idx(2:end)) = diff(Y(idx));
Y = reshape(cumsum(Y(:)), [], size(X, 1)).';   %'// Reshape back into a matrix

This works by treating the input data as a long vector, applying the original solution and then reshaping the result back into a matrix. The first column is always treated as non-zero so that the values don't propagate throughout rows. Also note that the original matrix is transposed so that it is converted to a vector in row-major order.

Answer 4

x=[0,1,2,2,1,0;
5,6,3,0,1,2;
1,1,1,1,0,1];
%Do it column by column is easier
x=x';
rm=0;
while 1
    %fields to replace
    l=(x==0);
    %do nothing for the first row/column
    l(1,:)=0;
    rm2=sum(sum(l));
    if rm2==rm
        %nothing to do
        break;
    else
        rm=rm2;
    end
    %replace zeros
    x(l) = x(find(l)-1);
end
x=x';

Answer 5

I have a function I use for a similar problem for filling NaNs. This can probably be cutdown or sped up further - it's extracted from pre-existing code that has a bunch more functionality (forward/backward filling, maximum distance etc).

X = [
    0 1 2 2 1 0
    5 6 3 0 0 2
    1 1 1 1 0 1
    0 0 4 5 3 9
];

X(X == 0) = NaN;
Y = nanfill(X,2);
Y(isnan(Y)) = 0

function y = nanfill(x,dim)
if nargin < 2, dim = 1; end
if dim == 2, y = nanfill(x',1)'; return; end
i = find(~isnan(x(:)));
j = 1:size(x,1):numel(x);
j = j(ones(size(x,1),1),:);
ix = max(rep([1; i],diff([1; i; numel(x) + 1])),j(:));
y = reshape(x(ix),size(x));

function y = rep(x,times)
i = find(times);
if length(i) < length(times), x = x(i); times = times(i); end
i = cumsum([1; times(:)]);
j = zeros(i(end)-1,1);
j(i(1:end-1)) = 1;
y = x(cumsum(j));