Circular City Tower Views
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.
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.
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].views of N integers, where views[i] is the total count of distinct towers j (j != i) visible from tower i.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]).
heights will not be empty. If N=1, no other towers exist, so the view count for that tower is 0.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]).N up to 10^5. An O(N^2) solution will likely time out.Examples
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):
min(heights[0], heights[2]) = min(3, 2) = 2. heights[1] = 1 < 2. So, 2 is visible.min(heights[0], heights[3]) = min(3, 4) = 3. heights[1] = 1 < 3 and heights[2] = 2 < 3. So, 3 is visible.min(heights[1], heights[3]) = min(1, 4) = 1. heights[2] = 2 is NOT < 1. So, 3 is NOT visible.min(heights[2], heights[0]) = min(2, 3) = 2. heights[1] = 1 < 2. So, 0 is visible.min(heights[3], heights[1]) = min(4, 1) = 1. heights[0] = 3 is NOT < 1. So, 1 is NOT visible.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.
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):
Constraints
1 <= N <= 10^51 <= heights[i] <= 10^9heights contains only positive integers.N=1, all towers having identical heights, or arrays with a single tallest tower.Loading editor...