Maximum total area occupied by pistons

Array Hash Table String Simulation Counting Prefix Sum

40.6% acceptance

Mar 31, 2026

There are several pistons in an old car engine, and we want to calculate the maximum possible area under the pistons. You are given: An integer height, representing the maximum height a piston can reach. An integer array positions, where positions[i] is the current position of piston i, which is equal to the current area under it. A string directions, where directions[i] is the current moving direction of piston i, 'U' for up, and 'D' for down. Each second: Every piston moves in its current direction 1 unit. e.g., if the direction is up, positions[i] is incremented by 1. If a piston has reached one of the ends, i.e., positions[i] == 0 or positions[i] == height, its direction will change. Return the maximum possible area under all the pistons.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_area(height: i32, positions: Vec<i32>, directions: String) -> i64 {
    let h = height as i64;
    let dirs: Vec<u8> = directions.into_bytes();
    let n = positions.len();

    let mut initial_area: i64 = 0;
    let mut velocity: i64 = 0;
    let mut events: Vec<(i64, i64)> = Vec::new();

    for i in 0..n {
      let p = positions[i] as i64;
      initial_area += p;

      if dirs[i] == b'U' {
        velocity += 1;
        events.push((h - p, -2));
        if p > 0 {
          events.push((2 * h - p, 2));
        }
      } else {
        velocity -= 1;
        events.push((p, 2));
        if p < h {
          events.push((p + h, -2));
        }
      }
    }

    events.sort_unstable();

    let mut current_area = initial_area;
    let mut current_time: i64 = 0;
    let mut max_area = initial_area;

    let mut idx = 0;
    while idx < events.len() {
      let t = events[idx].0;
      current_area += velocity * (t - current_time);
      current_time = t;
      max_area = max_area.max(current_area);

      while idx < events.len() && events[idx].0 == t {
        velocity += events[idx].1;
        idx += 1;
      }
    }

    max_area
  }
}