C-5.6 Suppose we have an nn two-dimensional array A that we want to use to store integers, but we dont want to spend the O(n²) work to initialize it to all 0s, because we already know that we are only going to use up to n of these cells in our algorithm, which itself runs in O(n) time (not counting the time to initialize A). Show how to use an array-based stack S storing (i, j,k) integer triples to allow us to use the array A without initializing it and still implement our algorithm in O(n) time, even though the initial values in the cells of A might be total garbage.

Extra: Initialization of an array in O(1) time.

Edit: The algorithm mentioned in the question is the one we are proposing. It is stack operations. Push and Pop answers the "Extra" (perhaps rather it is Peek) question given that they have a running time of O(1) but an algorithm that runs in O(n) is what the initial question asks for. Basically, we want a stack (array-based) that can access a certain row and column with a running time of O(n).