Maximum Building Height - Practice Coding Problems

Maximum Building Height - Problem

You want to build n new buildings in a city. The new buildings will be built in a line and are labeled from 1 to n.

However, there are city restrictions on the heights of the new buildings:

The height of each building must be a non-negative integer.
The height of the first building must be 0.
The height difference between any two adjacent buildings cannot exceed 1.

Additionally, there are city restrictions on the maximum height of specific buildings. These restrictions are given as a 2D integer array restrictions where restrictions[i] = [id_i, maxHeight_i] indicates that building id_i must have a height less than or equal to maxHeight_i.

It is guaranteed that each building will appear at most once in restrictions, and building 1 will not be in restrictions.

Return the maximum possible height of the tallest building.

Input & Output

Example 1 — Basic Case with Restriction

$ Input: n = 4, restrictions = [[2,1],[4,1]]

› Output: 2

💡 Note: Building heights: [0, 1, 0, 1]. Building 1 starts at 0, building 2 restricted to max 1, building 3 can be at most height 1+1=2 but must support building 4's max height of 1, so building 3 gets height 1+1-1=1, but actually building 3 can be height 2. Final optimal: [0, 1, 2, 1] with max height 2.

Example 2 — No Restrictions

$ Input: n = 5, restrictions = []

› Output: 2

💡 Note: Without restrictions, optimal heights are [0, 1, 2, 1, 0] or [0, 1, 2, 3, 2]. The maximum reachable height is limited by the need to return back considering adjacent differences, giving maximum height of 2 at position 3.

Example 3 — Multiple Restrictions

$ Input: n = 6, restrictions = [[3,0],[4,2]]

› Output: 1

💡 Note: Building 3 must be height 0, building 4 max height 2. Starting from building 1 at height 0, we can reach building 3 with height 0, then building 4 can be at most min(0+1, 2) = 1. Maximum achievable height is 1.

Constraints

1 ≤ n ≤ 10⁹
0 ≤ restrictions.length ≤ 1000
1 ≤ id_i ≤ n
0 ≤ maxHeight_i ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

n buildings with height restrictions and adjacency rules

Process

Two-pass optimization respecting all constraints

Output

Maximum height of tallest building

Key Takeaway

🎯 Key Insight: Two-pass optimization handles bidirectional adjacency constraints optimally

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Meta 6

The key insight is using a two-pass greedy approach to handle bidirectional constraints. Forward pass maximizes heights from left, backward pass ensures feasibility from right. Best approach is Greedy Two-Pass. Time: O(r log r + n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(n^n)	O(n)	Try all possible height assignments and validate constraints
Greedy Two-Pass	O(r log r + n)	O(n)	Build maximum heights in two passes: left-to-right, then right-to-left

Brute Force Simulation — Algorithm Steps

Generate all height combinations
Check adjacent height differences ≤ 1
Verify specific building restrictions
Find maximum height across valid combinations

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Try all height combinations for each building

Validate

Check adjacent differences and restrictions

Maximum

Find the tallest valid configuration

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int maxHeight = 0;

void backtrack(int pos, int* heights, int n, int restrictionMap[][2], int restrictionCount) {
    if (pos > n) {
        int max_h = 0;
        for (int i = 1; i <= n; i++) {
            if (heights[i] > max_h) max_h = heights[i];
        }
        if (max_h > maxHeight) maxHeight = max_h;
        return;
    }
    
    int maxAllowed = n;
    for (int i = 0; i < restrictionCount; i++) {
        if (restrictionMap[i][0] == pos) {
            maxAllowed = restrictionMap[i][1];
            break;
        }
    }
    
    for (int h = 0; h <= maxAllowed; h++) {
        if (pos == 1 && h != 0) continue;
        if (pos > 1) {
            int diff = h - heights[pos-1];
            if (diff < 0) diff = -diff;
            if (diff > 1) continue;
        }
        heights[pos] = h;
        backtrack(pos + 1, heights, n, restrictionMap, restrictionCount);
    }
}

int solution(int n, int restrictionMap[][2], int restrictionCount) {
    maxHeight = 0;
    int* heights = calloc(n + 1, sizeof(int));
    backtrack(1, heights, n, restrictionMap, restrictionCount);
    free(heights);
    return maxHeight;
}

int main() {
    int n;
    scanf("%d", &n);
    getchar();
    
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int restrictions[100][2];
    int restrictionCount = 0;
    
    if (strcmp(line, "[]\n") != 0) {
        char* ptr = line + 1;
        while (*ptr != ']' && *ptr != '\0') {
            if (*ptr == '[') {
                ptr++;
                sscanf(ptr, "%d,%d", &restrictions[restrictionCount][0], &restrictions[restrictionCount][1]);
                restrictionCount++;
                while (*ptr != ']' && *ptr != '\0') ptr++;
            }
            ptr++;
        }
    }
    
    printf("%d\n", solution(n, restrictions, restrictionCount));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n^n)

For each of n buildings, we try up to n possible heights

✓ Linear Growth

Space Complexity

O(n)

Store current height assignment

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler