LeetCode 2078. Two Furthest Houses With Different Colors Solution in Java, C++, Python & More | Explanation + Code

Description

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), where abs(x) is the absolute value of x.

 

Example 1:

Input: colors = [1,1,1,6,1,1,1]
Output: 3
Explanation: In the above image, color 1 is blue, and color 6 is red.
The furthest two houses with different colors are house 0 and house 3.
House 0 has color 1, and house 3 has color 6. The distance between them is abs(0 - 3) = 3.
Note that houses 3 and 6 can also produce the optimal answer.

Example 2:

Input: colors = [1,8,3,8,3]
Output: 4
Explanation: In the above image, color 1 is blue, color 8 is yellow, and color 3 is green.
The furthest two houses with different colors are house 0 and house 4.
House 0 has color 1, and house 4 has color 3. The distance between them is abs(0 - 4) = 4.

Example 3:

Input: colors = [0,1]
Output: 1
Explanation: The furthest two houses with different colors are house 0 and house 1.
House 0 has color 0, and house 1 has color 1. The distance between them is abs(0 - 1) = 1.

 

Constraints:

• n == colors.length
• 2 <= n <= 100
• 0 <= colors[i] <= 100
• Test data are generated such that at least two houses have different colors.

Solutions

Solution 1: Greedy

We can observe that if the first and last houses have different colors, the maximum distance is n - 1.

If the first and last houses have the same color, we can scan from the left to find the first house with a different color (let its index be i), and scan from the right to find the first house with a different color (let its index be j). The maximum distance is then max(n - i - 1, j).

The time complexity is O(n), where n is the number of houses. The space complexity is O(1).

PythonJavaC++GoTypeScriptRust

class Solution: def maxDistance(self, colors: List[int]) -> int: n = len(colors) if colors[0] != colors[-1]: return n - 1 i, j = 1, n - 2 while colors[i] == colors[0]: i += 1 while colors[j] == colors[0]: j -= 1 return max(n - i - 1, j)(code-box)

class Solution { public int maxDistance(int[] colors) { int n = colors.length; if (colors[0] != colors[n - 1]) { return n - 1; } int i = 1, j = n - 2; while (colors[i] == colors[0]) { ++i; } while (colors[j] == colors[0]) { --j; } return Math.max(n - i - 1, j); } }(code-box)

class Solution { public: int maxDistance(vector<int>& colors) { int n = colors.size(); if (colors[0] != colors[n - 1]) { return n - 1; } int i = 1, j = n - 2; while (colors[i] == colors[0]) { ++i; } while (colors[j] == colors[0]) { --j; } return max(n - i - 1, j); } };(code-box)

func maxDistance(colors []int) int { n := len(colors) if colors[0] != colors[n-1] { return n - 1 } i, j := 1, n-2 for colors[i] == colors[0] { i++ } for colors[j] == colors[0] { j-- } return max(n-i-1, j) }(code-box)

function maxDistance(colors: number[]): number { const n = colors.length; if (colors[0] !== colors[n - 1]) { return n - 1; } let [i, j] = [1, n - 2]; while (colors[i] === colors[0]) { i++; } while (colors[j] === colors[0]) { j--; } return Math.max(n - i - 1, j); }(code-box)

impl Solution { pub fn max_distance(colors: Vec<i32>) -> i32 { let n = colors.len(); if colors[0] != colors[n - 1] { return (n - 1) as i32; } let mut i = 1; while colors[i] == colors[0] { i += 1; } let mut j = n - 2; while colors[j] == colors[0] { j -= 1; } std::cmp::max((n - i - 1) as i32, j as i32) } }(code-box)