Suppose we have an nn two-dimensional array A that we want to use to store integers, but
Question:
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(n2) work to initialize it to all 0’s, 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.
Fantastic news! We've Found the answer you've been seeking!
Step by Step Answer:
Related Book For
Data Structures And Algorithms In C++
ISBN: 9780470383278
2nd Edition
Authors: Michael T. Goodrich, Roberto Tamassia, David M. Mount
Question Posted: