Frontend School

Maximal View Area

DSA
hard

Maximal View Area

Hard
Arrays
Stack
Monotonic Stack
Geometry

Overview

In urban development, understanding the "view area" for a building can be critical for factors like property valuation, light access, or even strategic drone placement. Imagine a city skyline where each building has a specific height. For any given building, we define its "view area" as the largest rectangular area it can form by extending horizontally to its left and right, constrained by the nearest buildings that are strictly taller than itself. If no strictly taller building exists on a side, the view extends to the edge of the city.

This problem challenges you to efficiently calculate the maximum possible "view area" among all buildings in the city.

What you need to do / Task

Implement the function maximalViewArea that takes an array of non-negative integers heights representing the heights of buildings. Your task is to calculate the maximum "view area" among all possible buildings.

For each building i (at index i):

  1. Find L_idx: the largest index l < i such that heights[l] > heights[i]. If no such building exists, L_idx = -1 (representing the left boundary of the city).
  2. Find R_idx: the smallest index r > i such that heights[r] > heights[i]. If no such building exists, R_idx = heights.length (representing the right boundary of the city).
  3. The "view area" for building i is calculated as heights[i] * (R_idx - L_idx - 1).

Your function should return the maximum "view area" found across all buildings.

Input & output

  • Input: heights: number[]
    • An array of non-negative integers, where heights[p] represents the height of the building at index p.
  • Output: number
    • The maximum "view area" found among all buildings.

Clarifications

  • An empty input array heights should result in a return value of 0.
  • Buildings are indexed from left to right, starting at 0.
  • The width calculation R_idx - L_idx - 1 correctly accounts for the indices and the inclusive nature of the building i itself.

Examples

1

Example 1

Input:

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

Output:

36

Note:

Let N = 6.

  • For building at index 0 (height 2): L_idx = -1, R_idx = 2 (heights[2]=5 > 2). Area = 2 * (2 - (-1) - 1) = 2 * 2 = 4.
  • For building at index 1 (height 1): L_idx = 0 (heights[0]=2 > 1), R_idx = 2 (heights[2]=5 > 1). Area = 1 * (2 - 0 - 1) = 1 * 1 = 1.
  • For building at index 2 (height 5): L_idx = -1, R_idx = 3 (heights[3]=6 > 5). Area = 5 * (3 - (-1) - 1) = 5 * 3 = 15.
  • For building at index 3 (height 6): L_idx = -1, R_idx = N=6. Area = 6 * (6 - (-1) - 1) = 6 * 6 = 36.
  • For building at index 4 (height 2): L_idx = 3 (heights[3]=6 > 2), R_idx = 5 (heights[5]=3 > 2). Area = 2 * (5 - 3 - 1) = 2 * 1 = 2.
  • For building at index 5 (height 3): L_idx = 3 (heights[3]=6 > 3), R_idx = N=6. Area = 3 * (6 - 3 - 1) = 3 * 2 = 6.

The maximum area found is 36.

2

Example 2

Input:

heights = [1, 2, 3, 4]

Output:

16

Note:

Let N = 4.

  • For building at index 0 (height 1): L_idx = -1, R_idx = 1 (heights[1]=2 > 1). Area = 1 * (1 - (-1) - 1) = 1 * 1 = 1.
  • For building at index 1 (height 2): L_idx = -1, R_idx = 2 (heights[2]=3 > 2). Area = 2 * (2 - (-1) - 1) = 2 * 2 = 4.
  • For building at index 2 (height 3): L_idx = -1, R_idx = 3 (heights[3]=4 > 3). Area = 3 * (3 - (-1) - 1) = 3 * 3 = 9.
  • For building at index 3 (height 4): L_idx = -1, R_idx = N=4. Area = 4 * (4 - (-1) - 1) = 4 * 4 = 16.

The maximum area found is 16.

3

Example 3

Input:

heights = [5, 5, 5]

Output:

15

Note:

Let N = 3.

  • For building at index 0 (height 5): L_idx = -1, R_idx = N=3. Area = 5 * (3 - (-1) - 1) = 5 * 3 = 15.
  • For building at index 1 (height 5): L_idx = -1, R_idx = N=3. Area = 5 * (3 - (-1) - 1) = 5 * 3 = 15.
  • For building at index 2 (height 5): L_idx = -1, R_idx = N=3. Area = 5 * (3 - (-1) - 1) = 5 * 3 = 15.

All buildings have the same height, so for each, its view extends to the city boundaries. The maximum area is 15.

Constraints

Constraints & assumptions

  • 0 <= heights.length <= 10^5
  • 0 <= heights[i] <= 10^9
  • The input array heights will only contain non-negative integers.

Out of scope

  • Input validation for non-array types or negative heights.

What interviewers evaluate

  • Correctness: The solution must accurately calculate the maximal view area according to the strict definition.
  • Efficiency: The solution should achieve optimal time and space complexity, typically O(N) time and O(N) space.
  • Edge Cases: Proper handling of empty arrays, arrays with a single element, or scenarios where no strictly taller elements exist on one or both sides.
  • Code Quality: Readability, maintainability, and clear structure of the implementation.

Loading editor...