Frontend School

Oracle's Skyline Influence Sum

DSA
medium

Oracle's Skyline Influence Sum

Medium
Arrays
Stack
Dynamic Programming
Monotonic Stack

Overview

In Oracle's urban planning division, we're analyzing the "influence" of buildings on their surroundings. For a given row of buildings, each with a specific height, we need to quantify the cumulative "influence" exerted by shorter buildings to its left. This metric helps us understand visual impact and potential development constraints.

What you need to do / Task

You are tasked with implementing a function calculateInfluenceSums that takes an array of building heights and returns an array where each element result[i] represents the "influence score" for the building at index i.

The "influence score" for a building at index i is defined as follows: result[i] is the sum of heights[j] for all j < i such that heights[j] is strictly shorter than heights[i], AND heights[j] is either the nearest strictly shorter building to heights[i] on its left, or it's the nearest strictly shorter building to another building heights[k] (where j < k < i) that itself contributes to heights[i]'s influence score. This forms a chain of shorter buildings leading up to heights[i].

More precisely, let prevSmaller[idx] be the index of the nearest building to the left of idx that has a strictly smaller height. If no such building exists, prevSmaller[idx] is -1. Then, result[i] can be recursively defined:

  • If prevSmaller[i] is -1, then result[i] = 0.
  • Otherwise, result[i] = heights[prevSmaller[i]] + result[prevSmaller[i]].

Input & output

Function Signature: function calculateInfluenceSums(heights: number[]): number[]

  • heights: An array of integers representing the heights of buildings. heights[i] is the height of the i-th building.
  • Returns: An array of integers result, where result[i] is the influence score for the building at index i, as defined above.

Clarifications

  • Empty Input: If heights is empty, return an empty array.
  • Single Building: If heights contains only one building, its influence score is 0.
  • All Same Height: If all buildings have the same height, all influence scores will be 0, as no building will be strictly shorter than its neighbor to its left.
  • Large N: The array heights can contain up to 10^5 elements. Your solution should be efficient enough to handle this scale.

Examples

1

Example 1

Input:

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

Output:

[0, 0, 1, 1, 3]

Note:

  • For heights[0]=3: No buildings to the left. Score = 0.
  • For heights[1]=1: No buildings to the left are strictly shorter. Score = 0.
  • For heights[2]=4: prevSmaller[2] is index 1 (heights[1]=1). Score = heights[1] + result[1] = 1 + 0 = 1.
  • For heights[3]=2: prevSmaller[3] is index 1 (heights[1]=1). Score = heights[1] + result[1] = 1 + 0 = 1.
  • For heights[4]=5: prevSmaller[4] is index 3 (heights[3]=2). Score = heights[3] + result[3] = 2 + 1 = 3.
2

Example 2

Input:

heights = [10, 5, 8, 3, 12]

Output:

[0, 0, 5, 0, 3]

Note:

  • For heights[0]=10: Score = 0.
  • For heights[1]=5: prevSmaller[1] is -1. Score = 0.
  • For heights[2]=8: prevSmaller[2] is index 1 (heights[1]=5). Score = heights[1] + result[1] = 5 + 0 = 5.
  • For heights[3]=3: prevSmaller[3] is -1. Score = 0.
  • For heights[4]=12: prevSmaller[4] is index 3 (heights[3]=3). Score = heights[3] + result[3] = 3 + 0 = 3.
3

Example 3

Input:

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

Output:

[0, 1, 3, 6, 10]

Note:

  • For heights[0]=1: Score = 0.
  • For heights[1]=2: prevSmaller[1] is index 0 (heights[0]=1). Score = heights[0] + result[0] = 1 + 0 = 1.
  • For heights[2]=3: prevSmaller[2] is index 1 (heights[1]=2). Score = heights[1] + result[1] = 2 + 1 = 3.
  • For heights[3]=4: prevSmaller[3] is index 2 (heights[2]=3). Score = heights[2] + result[2] = 3 + 3 = 6.
  • For heights[4]=5: prevSmaller[4] is index 3 (heights[3]=4). Score = heights[3] + result[3] = 4 + 6 = 10.

Constraints

Constraints & assumptions

  • 1 <= heights.length <= 10^5
  • 0 <= heights[i] <= 10^9
  • The sum of all influence scores might exceed a 32-bit integer. Use appropriate data types (e.g., number in TypeScript/JavaScript, which handles up to 2^53 - 1).

What interviewers evaluate

  • Correctness: The solution accurately computes the influence score for all buildings according to the problem definition.
  • Efficiency: The solution demonstrates optimal time and space complexity for the given constraints (O(N) time, O(N) space).
  • Algorithm Design: Proper application of a monotonic stack combined with dynamic programming principles.
  • Code Quality: Clean, readable, well-structured code with appropriate variable names.

Loading editor...