Chicago has many tall buildings, but only some of them have a clear view of Lake

Question

Chicago has many tall buildings, but only some of them have a clear view of Lake Michigan. Suppose we are given an array A[1.. n] that stores the height of n buildings on a city block, indexed from west to east. Building i has a good view of Lake Michigan if and only if every building to the east of i is shorter than i. Here is an algorithm that computes which buildings have a good view of Lake Michigan. What is the running time of this algorithm? GOODVIEW (1..n): initialize a stack S for i leftarrow 1 to n while (S not empty and A[i] > A[Top(S)]) POP(S) PUSH (S, i) return S

Explanation / Answer

Pop(s) has the running time complexity of O(1)

Push() has the running complexity of O(1)

For loop the time complexity will be t(n)

So total time complexity will be O( nlog n)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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