Coding Puzzle: Biggest Square in City Skyline

• Difficulty: Medium
• Patterns:
  • Dynamic Programming

Problem Definition

Given a city skyline represented by an array containing the height at each index, return the area of the biggest square that can be fit inside the skyline.

Examples

Some test cases to verify our solution.

assert(skyline_square_area([5555]) == 1)
assert(skyline_square_area([4, 3, 4]) == 9)
assert(skyline_square_area([1, 2, 3, 1, 1]) == 4)
assert(skyline_square_area([2, 1, 1, 5, 1, 16]) == 1)
assert(skyline_square_area([5, 5, 5]) == 9)
assert(skyline_square_area([7, 6, 5, 4, 3]) == 16)
assert(skyline_square_area([5, 1, 2, 1, 2, 1, 4, 1, 10]) == 1)
assert(skyline_square_area([9, 1, 3, 4, 3, 2, 1]) == 9)
assert(skyline_square_area([5, 5, 5, 4, 3]) == 16)
assert(skyline_square_area([5, 5, 5, 7, 6, 5, 4, 3]) == 25)
assert(skyline_square_area([5, 5, 5, 7, 6, 5, 4, 3, 9, 9, 9, 9, 9, 9, 9, 9]) == 64)
assert(skyline_square_area([5, 5, 5, 7, 6, 5, 4, 3, 9, 9, 9, 9, 9, 9, 9, 9, 9]) == 81)
assert(skyline_square_area([5, 5, 5, 7, 6, 5, 4, 3, 9, 9, 9, 9, 9, 9, 9, 9, 9, 55]) == 81)
assert(skyline_square_area([5, 5, 5, 7, 6, 5, 4, 3, 9, 9, 9, 9, 9, 9, 9, 9, 9, 5, 5, 7, 6, 5, 4, 3]) == 81)
assert(skyline_square_area([5, 5, 5, 7, 6, 5, 4, 3, 9, 9, 9, 9, 9, 9, 9, 9, 9, 5, 5, 7, 6, 5, 4, 3, 9, 9, 9, 9, 9, 9, 9, 9, 9]) == 81)

Solution

This is a dynamic programming problem, but we don't need to preserve a dp variable to compute a solution.

def skyline_square_area(arr):
    if not arr:
        return 0
    max_side = 0
    i = 0
    while i < len(arr):
        max_width = arr[i]
        width = 1
        nxt = None
        while i + width < len(arr) and width < max_width:
            if arr[i + width] < max_width:
                max_width = arr[i + width]
            elif nxt is None and arr[i + width] > max_width:
                nxt = i + width
            width += 1
        candidate = min(max_width, width)
        if candidate > max_side:
            max_side = candidate
        if nxt is None:
            i = i + width
        else:
            i = nxt
    return max_side**2

Complexity

Let $n = $ len(arr).

Then runtime complexity should be $O(n^2)$.

Auxiliary space complexity should be $O(1)$.