Frontend School

Circular City Tower Views

DSA
hard

Circular City Tower Views

Hard
Monotonic Stack
Arrays
Circular Array

Overview

Imagine a smart city planning system where unobstructed line of sight is crucial for communication, sensor networks, or even aesthetic evaluations. You're tasked with developing an algorithm for Zoho's urban planning software to assess tower visibility in a circular city layout. This problem challenges your ability to apply data structures efficiently to handle complex spatial relationships and circular constraints, a common requirement in real-world geospatial and network optimization scenarios.

What you need to do / Task

Implement a function circularCityTowerViews that takes an array of tower heights in a circular arrangement and returns an array where each element i represents the count of towers visible from tower i.

Input & output

  • heights: An array of positive integers heights[0...N-1], where heights[i] is the height of the i-th tower. The towers are arranged in a circle, meaning heights[N-1] is adjacent to heights[0].
  • Return: An array views of N integers, where views[i] is the total count of distinct towers j (j != i) visible from tower i.

Visibility Rule:

A tower j is visible from tower i if all towers k strictly between i and j (in either clockwise or counter-clockwise direction) have heights[k] < min(heights[i], heights[j]).

Clarifications

  • Empty or single-tower input: The input array heights will not be empty. If N=1, no other towers exist, so the view count for that tower is 0.
  • Identical heights: If heights[i] == heights[j], the visibility rule still applies with min(heights[i], heights[j]) being heights[i]. Towers of identical height can block each other if their height is not strictly less than min(heights[i], heights[j]).
  • Large N: Your solution should be efficient enough to handle N up to 10^5. An O(N^2) solution will likely time out.

Examples

1

Example 1

Input:

heights = [3, 1, 2, 4]

Output:

[3, 2, 3, 2]

Note:

Let's trace for heights = [3, 1, 2, 4] (indices 0, 1, 2, 3):

  • From Tower 0 (height 3):
    • To 1 (height 1): Visible (no towers between).
    • To 2 (height 2): Clockwise, tower 1 (height 1) is between. min(heights[0], heights[2]) = min(3, 2) = 2. heights[1] = 1 < 2. So, 2 is visible.
    • To 3 (height 4): Clockwise, towers 1 (height 1) and 2 (height 2) are between. min(heights[0], heights[3]) = min(3, 4) = 3. heights[1] = 1 < 3 and heights[2] = 2 < 3. So, 3 is visible.
    • Total visible from 0: {1, 2, 3}. Count = 3.
  • From Tower 1 (height 1):
    • To 0 (height 3): Visible (no towers between).
    • To 2 (height 2): Visible (no towers between).
    • To 3 (height 4): Clockwise, tower 2 (height 2) is between. min(heights[1], heights[3]) = min(1, 4) = 1. heights[2] = 2 is NOT < 1. So, 3 is NOT visible.
    • Total visible from 1: {0, 2}. Count = 2.
  • From Tower 2 (height 2):
    • To 0 (height 3): Counter-clockwise, tower 1 (height 1) is between. min(heights[2], heights[0]) = min(2, 3) = 2. heights[1] = 1 < 2. So, 0 is visible.
    • To 1 (height 1): Visible.
    • To 3 (height 4): Visible.
    • Total visible from 2: {0, 1, 3}. Count = 3.
  • From Tower 3 (height 4):
    • To 0 (height 3): Visible.
    • To 1 (height 1): Clockwise, tower 0 (height 3) is between. min(heights[3], heights[1]) = min(4, 1) = 1. heights[0] = 3 is NOT < 1. So, 1 is NOT visible.
    • To 2 (height 2): Visible.
    • Total visible from 3: {0, 2}. Count = 2.
2

Example 2

Input:

heights = [5, 5, 5, 5]

Output:

[0, 0, 0, 0]

Note:

For any two distinct towers i and j, min(heights[i], heights[j]) = 5. Any tower k strictly between i and j will also have heights[k] = 5. Since heights[k] < min(heights[i], heights[j]) (i.e., 5 < 5) is false, no tower is visible from any other tower.

3

Example 3

Input:

heights = [1, 2, 3, 2, 1]

Output:

[2, 3, 2, 3, 2]

Note:

Let's trace for heights = [1, 2, 3, 2, 1] (indices 0-4):

  • From Tower 0 (height 1):
    • Visible: {1 (height 2), 4 (height 1)}. Count = 2.
    • Blocked by tower 1 (height 2) for any other clockwise view; blocked by tower 4 (height 1) for tower 3.
  • From Tower 1 (height 2):
    • Visible: {0 (height 1), 2 (height 3), 3 (height 2)}. Count = 3.
  • From Tower 2 (height 3):
    • Visible: {1 (height 2), 3 (height 2)}. Count = 2.
    • Blocked by tower 1 (height 2) for tower 0; blocked by tower 3 (height 2) for tower 4.
  • From Tower 3 (height 2): Symmetric to Tower 1. Count = 3.
  • From Tower 4 (height 1): Symmetric to Tower 0. Count = 2.

Constraints

Constraints & assumptions

  • 1 <= N <= 10^5
  • 1 <= heights[i] <= 10^9
  • The input array heights contains only positive integers.
  • The towers are arranged in a perfect circle.

Out of scope

  • Input validation (e.g., negative heights, non-integer inputs).

What interviewers evaluate

  • Correctness: Accurate calculation of visible towers for all indices, adhering strictly to the visibility rule.
  • Efficiency: Optimal time complexity (ideally O(N)) and space complexity (O(N)).
  • Edge Cases: Robust handling of scenarios like N=1, all towers having identical heights, or arrays with a single tallest tower.
  • Code Quality: Clarity, readability, and structure of the code, including proper and idiomatic use of data structures like a Monotonic Stack.

Loading editor...