Frontend School

Dynamic Vista Score

DSA
hard

Dynamic Vista Score

Hard
Monotonic Stack
Arrays

Overview

In urban planning and telecommunications, optimizing the placement of communication towers is crucial for maximizing signal coverage and network efficiency. Consider a scenario where a city's skyline is represented by a sequence of tower heights. We want to identify the tower that offers the most 'dynamic vista' – a measure reflecting the combined impact of taller, unblocked towers it can observe, weighted by their height and distance. This problem challenges you to develop an algorithm that can quantify and find the maximum such vista score, which is vital for strategic planning.

What you need to do / Task

You are tasked with implementing a function maxDynamicVistaScore that takes an array of tower heights and returns the highest Dynamic Vista Score found among all towers. For each tower i, its Dynamic Vista Score is calculated as follows:

  1. Identify 'Visible' Towers: A tower j is considered 'visible' from tower i (where j != i) if heights[j] > heights[i] AND all towers k strictly between i and j (i.e., min(i,j) < k < max(i,j)) have heights[k] < heights[i]. In simpler terms, j must be the closest tower to i in its direction (left or right) that is strictly taller than i.
  2. Calculate Contribution: For each such visible tower j, it contributes heights[j] * (abs(i - j) + 1) to tower i's score. The (abs(i - j) + 1) term represents the 'distance factor', where a distance of 1 means adjacent towers.
  3. Sum Contributions: The Dynamic Vista Score for tower i is the sum of these contributions from all visible towers j (both to its left and right).
  4. Find Maximum: Your function should return the maximum Dynamic Vista Score found across all towers in the input array. If no towers are visible from any tower, the maximum score is 0.

Input & output

Function Signature:

function maxDynamicVistaScore(heights: number[]): number
  • heights: An array of non-negative integers representing tower heights.
  • Returns: A single non-negative integer, representing the maximum Dynamic Vista Score found.

Clarifications

  • Empty or Single Tower Input: If heights is empty or contains only one tower, no other towers can be visible, so the maximum score should be 0.
  • All Same Heights: If all towers have the same height, no tower can be 'strictly taller' than another, so the maximum score is 0.
  • Zero Height: Towers can have a height of 0. A tower with height 0 can potentially see taller towers, but it itself cannot be seen by any tower with height 0 or less.
  • Duplicate Heights: If heights[j] == heights[i], tower j is NOT visible from i according to the definition (it must be strictly taller).

Examples

1

Example 1

Input:

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

Output:

18

Note:

Let's calculate the score for each tower:

  • Tower 0 (height 3): Only tower 2 (height 4) is visible to the right (distance 2). Tower 4 (height 5) is blocked by tower 2. Score = 4 * (abs(0-2)+1) = 4 * 3 = 12.
  • Tower 1 (height 1): Tower 0 (height 3) is visible to the left (distance 1). Tower 2 (height 4) is visible to the right (distance 1). Score = 3 * (abs(1-0)+1) + 4 * (abs(1-2)+1) = 32 + 42 = 6 + 8 = 14.
  • Tower 2 (height 4): Only tower 4 (height 5) is visible to the right (distance 2). Score = 5 * (abs(2-4)+1) = 5 * 3 = 15.
  • Tower 3 (height 2): Tower 2 (height 4) is visible to the left (distance 1). Tower 4 (height 5) is visible to the right (distance 1). Score = 4 * (abs(3-2)+1) + 5 * (abs(3-4)+1) = 42 + 52 = 8 + 10 = 18.
  • Tower 4 (height 5): No taller towers are visible to its left or right. Score = 0. The maximum Dynamic Vista Score is 18.
2

Example 2

Input:

heights = [5,5,5,5]

Output:

0

Note:

Since no tower is strictly taller than any other tower, no towers are considered visible. Therefore, all scores are 0, and the maximum is 0.

3

Example 3

Input:

heights = [7,6,5,4,3,2,1,8]

Output:

70

Note:

For each tower, we find its closest strictly taller tower to the left and right. For instance:

  • Tower 0 (height 7): Only tower 7 (height 8) is visible to the right. Score = 8 * (abs(0-7)+1) = 8 * 8 = 64.
  • Tower 1 (height 6): Tower 0 (height 7) is visible to the left. Tower 7 (height 8) is visible to the right. Score = 7 * (abs(1-0)+1) + 8 * (abs(1-7)+1) = 72 + 87 = 14 + 56 = 70.
  • ...and so on. The maximum score among all towers is 70.

Constraints

Constraints & assumptions

  • 0 <= heights.length <= 10^5
  • 0 <= heights[i] <= 10^9
  • The solution should aim for O(N) time complexity, where N is the number of towers.
  • The solution should aim for O(N) space complexity.

Out of scope

  • Input validation (e.g., heights will always be an array of numbers).
  • Handling non-integer or negative tower heights.
  • Optimizing for extremely sparse or dense height distributions beyond the general O(N) solution.

What interviewers evaluate

  • Correct application of monotonic stack for efficient identification of visible towers.
  • Ability to correctly combine contributions from left and right visible towers.
  • Clear, well-structured, and readable code, demonstrating good software engineering practices.
  • Robustness in handling edge cases (empty array, single tower, no visible towers).
  • Achieving optimal O(N) time and O(N) space complexity.

Loading editor...