Suppose we have an n*n two-dimensional array A that we want to use to store inte

Question

Suppose we have an n*n two-dimensional array A that we want to use to store intergers, but we don't want to spend the O(n^2) work to initialize it to all 0's (the way Java dose), 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 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.

Explanation / Answer

Solution costing O(n) time and O(n) space:

For each element A[j], we need to know whether there is a smaller element on its left side. If there is not a smaller element on the left side, A[j] itself is the smallest of all elements from the leftmost element to A[j]. If there is a smaller element on the left side, the smallest of all elements from the leftmost element to A[j] is on the left side of A[j].

Therefore, we could construct an auxiliary array B. The element B[j] stores the index of the smallest element of elements from the leftmost element to A[j]. The array B can be constructed based on elements in A from left to right.

Similarly, we could also construct another auxiliary array C. The element C[j] stores the index of the greatest element of elements from the rightmost element to A[j]. The array C can be constructed based on elements in A from right to left.

When an element A[j] is scanned, the index j is compared with B[j] and C[j]. if B[j]<j(there is a smaller element on the left side) and j<C[j] (there is a greater element on the right side), three increasing elements have been found.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.