Longest Park

Tags

Longest Park

Category

Stacks

Difficulty

Hard

Problem Statement

Given an array of building heights along a street, find the longest contiguous "park" segment. A park is defined as a segment between two buildings where all intermediate buildings are strictly shorter than both endpoint buildings. Return the length of the longest such park (including the endpoints). This is solved efficiently using a monotonic stack approach.

Intuition

For each building, we want to know the nearest building to its left and right that is at least as tall. These two taller buildings can serve as endpoints of a park, with the current building and its neighbors forming the interior. A monotonic stack lets us efficiently find, for each position, the nearest greater or equal element on both sides. The park length between two "bounding" buildings is determined by the distance between them.

Approach

  1. Compute left bounds: Use a monotonic decreasing stack scanning left to right. For each index i, find the nearest index j < i where heights[j] >= heights[i]. Store in leftBound[i].
  2. Compute right bounds: Use a monotonic decreasing stack scanning right to left. For each index i, find the nearest index k > i where heights[k] >= heights[i]. Store in rightBound[i].
  3. For each index i, consider it as the minimum of a potential park. The park spans from leftBound[i] to rightBound[i], with length rightBound[i] - leftBound[i] + 1.
  4. Return the maximum such length across all indices.

Alternatively, use a single monotonic stack pass:

  1. Maintain a stack of indices with decreasing heights.
  2. When pushing index i, pop all indices with heights less than heights[i]. For each popped index, the current index i is its right bound and the new stack top is its left bound.
  3. Track the maximum park length from these bounds.

Pseudocode

function longestPark(heights):
    n = length(heights)
    leftBound = array of size n, initialized to -1
    rightBound = array of size n, initialized to n
    maxLength = 0

    // Find nearest greater or equal to the left
    stack = []
    for i from 0 to n - 1:
        while stack is not empty and heights[stack.top()] < heights[i]:
            stack.pop()
        if stack is not empty:
            leftBound[i] = stack.top()
        stack.push(i)

    // Find nearest greater or equal to the right
    stack = []
    for i from n - 1 down to 0:
        while stack is not empty and heights[stack.top()] < heights[i]:
            stack.pop()
        if stack is not empty:
            rightBound[i] = stack.top()
        stack.push(i)

    // Find longest park
    for i from 0 to n - 1:
        if leftBound[i] != -1 and rightBound[i] != n:
            parkLength = rightBound[i] - leftBound[i] + 1
            maxLength = max(maxLength, parkLength)

    return maxLength

Time & Space Complexity

  • Time: O(n) — Each element is pushed and popped from the stack at most once per pass. Three linear passes total.
  • Space: O(n) — For the stack and the boundary arrays.

Key Insights

  • The monotonic stack efficiently solves "nearest greater element" queries, which are the foundation of this problem.
  • The park definition requires both endpoints to be taller than all interior elements. This maps directly to finding left and right bounds that are greater or equal.
  • A single-pass monotonic stack solution is possible but the two-pass version is clearer and has the same asymptotic complexity.
  • This problem is structurally related to the largest rectangle in histogram problem, using the same monotonic stack framework.

Edge Cases

  • Array with fewer than 3 elements: the minimum valid park is the array itself if it satisfies the constraints, otherwise no park exists.
  • All buildings have the same height: every pair of adjacent buildings forms a valid park of length 2.
  • Strictly increasing or decreasing heights: parks can only form with the tallest building as one endpoint.
  • Multiple parks of the same maximum length: return the length (not the position).
  • Single building: no park possible, return 0.

Linked mentions