Large size of Matrix handling(interview question)

[codebusters]

I just had an interview where I was given a size m x n and asked to create a matrix. Each field in the matrix is either true or false and asked to calculate how many true fields are there around each field. But then he told me what will I do for very large number of m and n. Earlier I just created a matrix and looped over it. But he was telling me that I don't need the entire field all at once. How should I have answered that?
Thanks,

[helios]

He wanted what is known as a sparse matrix. Something simple to implement could be std::map<std::pair<int, int>, bool>. There are more complicated structures that can optimize memory usage when the number of non-default cells is large, and/or when the non-default cells tend to be clustered together.

[JLBorges]

> Each field in the matrix is either true or false
> and asked to calculate how many true fields are there around each field.

For each field, to calculate how many true fields are there around each field, we only need to hold a maximum of three rows and three columns in memory.

If the number of columns is not prohibitively large, a simple solution is to hold three complete rows in memory and calculate how many true fields are there around each field in the middle row.
Once this is done, throw away the top row, read (or create) the next row, and repeat.

(To avoid special-casing for the fields at the edges, we could treat it as an (m+2) x (n+2) matrix, with the fields at the edges set to false).

[codebusters]

@helios
@JLBorges
Thanks for the replies guys. I told them at each time we need 2 rows with n columns. I guess I went wrong there. Great replies!