Two furthest houses with different colors

Array Greedy

65.5% acceptance

Feb 25, 2026

1020

There are n houses evenly lined up on the street, and each house is beautifully painted. You are given a 0-indexed integer array colors of length n, where colors[i] represents the color of the ith house. Return the maximum distance between two houses with different colors. The distance between the ith and jth houses is abs(i - j).

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_distance(colors: Vec<i32>) -> i32 {
    let n = colors.len();
    let mut ans = 0;
    // Fix left at 0 and scan from right
    for j in (1..n).rev() {
      if colors[j] != colors[0] {
        ans = ans.max(j as i32);
        break;
      }
    }
    // Fix right at n-1 and scan from left
    for i in 0..n - 1 {
      if colors[i] != colors[n - 1] {
        ans = ans.max((n - 1 - i) as i32);
        break;
      }
    }
    ans
  }
}