Formatted question description: https://leetcode.ca/all/2078.html

# 2078. Two Furthest Houses With Different Colors (Easy)

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 `i`

house.^{th}

Return *the maximum distance between two houses with different colors*.

The distance between the `i`

and ^{th}`j`

houses is ^{th}`abs(i - j)`

, where `abs(x)`

is the **absolute value** of `x`

.

**Example 1:**

Input:colors = [,1,1,1,1,1,1]6Output:3Explanation: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 = [,8,3,8,1]3Output:4Explanation: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]1Output:1Explanation: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.

**Similar Questions**:

- Replace Elements with Greatest Element on Right Side (Easy)
- Maximum Distance Between a Pair of Values (Medium)
- Maximum Difference Between Increasing Elements (Easy)

## Solution 1. Map

For each `A[i]`

:

- If this is the first occurrence of this value, store
`A[i] -> i`

in a map`m`

. - Loop through each
`num, index`

pair the map`m`

and calculate the maximum`i - index`

value if`num != A[i]`

.

```
// OJ: https://leetcode.com/problems/two-furthest-houses-with-different-colors/
// Time: O(NM) where `N` is the length of `A` and `M` is the range of numbers in `A`.
// Space: O(M)
class Solution {
public:
int maxDistance(vector<int>& A) {
unordered_map<int, int> m; // first occurrence index
int ans = 0;
for (int i = 0; i < A.size(); ++i) {
if (m.count(A[i]) == 0) m[A[i]] = i;
for (auto &[c, j] : m) {
if (c != A[i]) {
ans = max(ans, i - j);
}
}
}
return ans;
}
};
```

Or use array.

```
// OJ: https://leetcode.com/problems/two-furthest-houses-with-different-colors/
// Time: O(NM) where `N` is the length of `A` and `M` is the range of numbers in `A`.
// Space: O(M)
class Solution {
public:
int maxDistance(vector<int>& A) {
int ans = 0, index[101] = {[0 ... 100] = -1};
for (int i = 0; i < A.size(); ++i) {
if (index[A[i]] == -1) index[A[i]] = i;
for (int j = 0; j <= 100; ++j) {
if (index[j] != -1 && j != A[i]) {
ans = max(ans, i - index[j]);
}
}
}
return ans;
}
};
```

## Solution 2. Mono-increasing Index Array

For each `A[i]`

:

- If this is the first occurrence of this value, push
`i`

into a`vector<int> index`

. - Loop through each index value
`j`

in`index`

array, and update answer with`i - j`

for the first`A[j] != A[i]`

. This step at most looks at two indices, so it’s`O(1)`

time.

```
// OJ: https://leetcode.com/problems/two-furthest-houses-with-different-colors/
// Time: O(N) where `N` is the length of `A` and `M` is the range of numbers in `A`.
// Space: O(M)
class Solution {
public:
int maxDistance(vector<int>& A) {
vector<int> index; // first occurrence index
int ans = 0, seen[101] = {};
for (int i = 0; i < A.size(); ++i) {
if (!seen[i]) {
seen[i] = 1;
index.push_back(i);
}
for (int j : index) {
if (A[j] != A[i]) {
ans = max(ans, i - j);
break;
}
}
}
return ans;
}
};
```

## Discuss

https://leetcode.com/problems/two-furthest-houses-with-different-colors/discuss/1589010/C%2B%2B-O(N)-Time-One-Pass