{x}
blog image

Two Furthest Houses With Different Colors

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.

Problem: Two Furthest Houses With Different Colors

The problem asks to find the maximum distance between two houses with different colors. The input is an array colors where colors[i] represents the color of the i-th house. The distance between two houses i and j is abs(i - j).

Solution Approaches and Code Explanations

Two approaches are presented: a brute-force approach and an optimized approach.

Approach 1: Brute Force

This approach iterates through all pairs of houses and checks if their colors are different. If they are, it updates the maximum distance found so far.

Time Complexity: O(n^2), where n is the number of houses. This is because we have nested loops iterating through all possible pairs. Space Complexity: O(1), as we only use a few variables to store the maximum distance and iterate.

Code:

  • 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
  • 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;
    }
}
  • C++:
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;
    }
};
  • Go:
func maxDistance(colors []int) int {
	ans, n := 0, len(colors)
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			if colors[i] != colors[j] {
				ans = max(ans, abs(i-j))
			}
		}
	}
	return ans
}
 
func abs(x int) int {
	if x >= 0 {
		return x
	}
	return -x
}

Approach 2: Optimized Approach

This approach leverages the fact that the maximum distance will either be between the first and last house if they have different colors, or it will be between the first house and the furthest house with a different color, or the last house and the furthest house with a different color. This reduces the time complexity significantly.

Time Complexity: O(n), where n is the number of houses. We only iterate through the array a few times. Space Complexity: O(1), as we only use a few variables.

Code:

  • Python:
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)
  • Java:
class Solution {
    public int maxDistance(int[] colors) {
        int n = colors.length;
        if (colors[0] != colors[n - 1]) {
            return n - 1;
        }
        int i = 0, j = n - 1;
        while (colors[++i] == colors[0])
            ;
        while (colors[--j] == colors[0])
            ;
        return Math.max(n - i - 1, j);
    }
}
  • C++:
class Solution {
public:
    int maxDistance(vector<int>& colors) {
        int n = colors.size();
        if (colors[0] != colors[n - 1]) return n - 1;
        int i = 0, j = n;
        while (colors[++i] == colors[0])
            ;
        while (colors[--j] == colors[0])
            ;
        return max(n - i - 1, j);
    }
};
  • Go:
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)
}

The optimized approach is significantly faster for larger input arrays. The brute force approach is easier to understand but becomes inefficient for large datasets. Choose the approach based on the size of the input data and the trade-off between code readability and efficiency.