LeetCode Entry
2078. Two Furthest Houses With Different Colors
Max distance between different numbers
2078. Two Furthest Houses With Different Colors easy substack youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/1334
Problem TLDR
Max distance between different numbers #easy
Intuition
Brute-force.
Clever solution: first or last is guaranteed to be included (if first==last its entire size, if first!=last then there is a third color in-between).
Approach
- scan all indices, pick max to first or last
- downsize the max length while prefix and suffix of this length is not good
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(1)\)
Code
// 14ms
fun maxDistance(c: IntArray) =
c.indices.last { c[0]!=c[it] || c.last()!=c[c.size-1-it] }
// 0ms
pub fn max_distance(c: Vec<i32>) -> i32 {
let n=c.len()-1; (0..n+1).rposition(|l|c[0]!=c[l]||c[n]!=c[n-l]).unwrap() as _
}