Amount of new area painted each day

Array Segment Tree Ordered Set

55.6% acceptance

Mar 31, 2026

440

No description available.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn amount_painted(paint: Vec<Vec<i32>>) -> Vec<i32> {
    // Jump / path compression approach
    let max_val = 50001;
    let mut jump = vec![0usize; max_val]; // jump[i] = the next unpainted position >= i
    for i in 0..max_val {
      jump[i] = i;
    }
    
    let mut result = Vec::with_capacity(paint.len());
    
    for p in &paint {
      let start = p[0] as usize;
      let end = p[1] as usize;
      let mut count = 0;
      let mut pos = Self::find(&mut jump, start);
      while pos < end {
        count += 1;
        jump[pos] = pos + 1; // mark as painted, point to next
        pos = Self::find(&mut jump, pos + 1);
      }
      result.push(count);
    }
    
    result
  }
  
  fn find(jump: &mut Vec<usize>, x: usize) -> usize {
    if jump[x] != x {
      jump[x] = Self::find(jump, jump[x]);
    }
    jump[x]
  }
}