Problem

Suppose we have an n × n two-dimensional array A that we want to use to store integers, but we don't want to spend the O(n 2 ) work to initialize it to all 0's (the way Java does), because we know in advance 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 arraybased 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.