# Two Furthest Houses With Different Colors
**Difficulty:** EASY
[External](https://leetcode.com/problems/two-furthest-houses-with-different-colors)
Canonical: https://scaleengineer.com/dsa/problems/two-furthest-houses-with-different-colors
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
**Companies:** [Visa](https://scaleengineer.com/companies/visa)
---
## Problem
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:**

![](https://assets.glich.co/dsa/two-furthest-houses-with-different-colors/image0.png) 

**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:**

![](https://assets.glich.co/dsa/two-furthest-houses-with-different-colors/image1.png) 

**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.

# Approaches
## Brute Force
The most straightforward approach is to check every possible pair of houses. We can use nested loops to iterate through all combinations of two distinct houses, `i` and `j`, and calculate the distance between them if their colors are different. We keep track of the maximum distance found.
**Time:** O(n^2), where `n` is the number of houses. The nested loops lead to a number of comparisons proportional to n * n. · **Space:** O(1), as it only uses a few variables to store the indices and the maximum distance, requiring constant extra space.
**Pros:** Simple to understand and implement.; Guaranteed to find the correct answer as it checks all possibilities.
**Cons:** Inefficient due to its quadratic time complexity. For larger values of `n` (though not in this problem's constraints), this approach would be too slow.
### Explanation
This method systematically explores all potential pairs of houses to find the one with the maximum distance and different colors. 

- We initialize a variable, `maxDistance`, to store the maximum distance, starting at 0.
- The outer loop selects the first house, `i`, starting from index 0 up to `n-1`.
- The inner loop selects the second house, `j`, starting from `i+1` to `n-1`. This ensures that each pair `(i, j)` is considered only once and `j > i`, so the distance is simply `j - i`.
- For each pair, we compare their colors, `colors[i]` and `colors[j]`. 
- If the colors are not the same, we update `maxDistance` with `Math.max(maxDistance, j - i)`.
- After the loops complete, `maxDistance` will hold the largest distance found between any two houses of different colors.

```java
class Solution {
    public int maxDistance(int[] colors) {
        int n = colors.length;
        int maxDistance = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (colors[i] != colors[j]) {
                    maxDistance = Math.max(maxDistance, j - i);
                }
            }
        }
        return maxDistance;
    }
}
```
### Algorithm
- Initialize a variable `maxDistance` to 0.
- Use a nested loop. The outer loop iterates through each house `i` from `0` to `n-1`.
- The inner loop iterates through each subsequent house `j` from `i + 1` to `n-1`.
- Inside the inner loop, check if `colors[i]` is different from `colors[j]`.
- If they are different, calculate the distance `j - i`.
- Update `maxDistance` to be the maximum of its current value and the newly calculated distance.
- After iterating through all pairs, return `maxDistance`.

## Greedy Two-Scan Approach
A more efficient, greedy approach recognizes that the pair of houses with the maximum distance must include one of the endpoints. If the houses at index `0` and `n-1` have different colors, the answer is `n-1`, which is the largest possible distance. If they have the same color, the optimal pair must be between one of the endpoints and some other house. This allows us to solve the problem in linear time.
**Time:** O(n), where `n` is the number of houses. We perform at most two linear scans of the array, and each scan stops as soon as it finds a match. · **Space:** O(1), as we only use a constant number of variables regardless of the input size.
**Pros:** Highly efficient with a linear time complexity.; Optimal solution for this problem.; Simple implementation with two single-pass loops.
**Cons:** The greedy logic, while correct, might be less intuitive to come up with compared to the brute-force method.
### Explanation
The core insight is that for any pair of houses `(i, j)` that are not endpoints, we can always extend the distance by choosing an endpoint instead. For example, the distance `j - 0` is greater than or equal to `j - i`. This means the optimal pair must involve either house `0` or house `n-1`.

Based on this, we only need to check two scenarios:
1.  The maximum distance from the house at index `0`. We find this by iterating from the end of the array (`j = n-1`) backwards. The first house `j` we encounter with `colors[j] != colors[0]` gives the maximum possible distance from house `0`, which is `j`. 
2.  The maximum distance from the house at index `n-1`. We find this by iterating from the start of the array (`i = 0`) forwards. The first house `i` we find with `colors[i] != colors[n-1]` gives the maximum possible distance from house `n-1`, which is `(n-1) - i`.

The overall maximum distance is the larger of these two values.

```java
class Solution {
    public int maxDistance(int[] colors) {
        int n = colors.length;
        int maxDist = 0;

        // Case 1: Find the furthest house from index 0 with a different color.
        // We scan from the right end to find the largest possible distance.
        for (int j = n - 1; j > 0; j--) {
            if (colors[j] != colors[0]) {
                maxDist = j; // Distance is j - 0
                break;
            }
        }

        // Case 2: Find the furthest house from index n-1 with a different color.
        // We scan from the left end to find the largest possible distance.
        for (int i = 0; i < n - 1; i++) {
            if (colors[i] != colors[n - 1]) {
                // Distance is (n - 1) - i
                maxDist = Math.max(maxDist, (n - 1) - i);
                break;
            }
        }
        
        return maxDist;
    }
}
```
### Algorithm
- The maximum possible distance must involve at least one of the two endpoints (house at index `0` or house at index `n-1`).
- This simplifies the problem into finding the maximum of two potential distances:
  1. The distance between the first house (index `0`) and the furthest house from it with a different color.
  2. The distance between the last house (index `n-1`) and the furthest house from it with a different color.
- To find the first distance, we scan from the right end of the array (`j = n-1`) to find the first house `j` where `colors[j] != colors[0]`. The distance is `j - 0`.
- To find the second distance, we scan from the left end of the array (`i = 0`) to find the first house `i` where `colors[i] != colors[n-1]`. The distance is `(n-1) - i`.
- The final answer is the maximum of these two calculated distances.

# Solutions
### Java

```java
class Solution {
public
  int maxDistance(int[] colors) {
    int ans = 0, n = colors.length;
    for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
        if (colors[i] != colors[j]) {
          ans = Math.max(ans, Math.abs(i - j));
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxDistance(vector<int> &colors) {
    int ans = 0, n = colors.size();
    for (int i = 0; i < n; ++i)
      for (int j = i + 1; j < n; ++j)
        if (colors[i] != colors[j])
          ans = max(ans, abs(i - j));
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxDistance(self, colors: List[int]) -> int: ans, n = 0, len(colors) for i in range(n): for j in range(i + 1, n): if colors[i] != colors[j]: ans = max(ans, abs(i - j)) return ans

```