Maximum building height

Array Math Sorting

38.3% acceptance

Feb 25, 2026

404

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] = [idi, maxHeighti] indicates that building idi must have a height less than or equal to maxHeighti. 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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_building(n: i32, mut restrictions: Vec<Vec<i32>>) -> i32 {
    // Add boundary: building 1 height 0, building n unconstrained
    restrictions.push(vec![1, 0]);
    restrictions.push(vec![n, n - 1]);
    restrictions.sort_unstable_by_key(|r| r[0]);

    let m = restrictions.len();

    // Forward pass: cap each restriction by what's reachable from left
    for i in 1..m {
      let dist = restrictions[i][0] - restrictions[i - 1][0];
      restrictions[i][1] = restrictions[i][1].min(restrictions[i - 1][1] + dist);
    }

    // Backward pass: cap each restriction by what's reachable from right
    for i in (0..m - 1).rev() {
      let dist = restrictions[i + 1][0] - restrictions[i][0];
      restrictions[i][1] = restrictions[i][1].min(restrictions[i + 1][1] + dist);
    }

    // Find max height achievable between consecutive restrictions
    let mut ans = 0i32;
    for i in 0..m - 1 {
      let h1 = restrictions[i][1];
      let h2 = restrictions[i + 1][1];
      let dist = restrictions[i + 1][0] - restrictions[i][0];
      // Peak between two endpoints: (h1 + h2 + dist) / 2
      let peak = (h1 + h2 + dist) / 2;
      ans = ans.max(peak);
    }
    ans
  }
}