Two Furthest Houses With Different Colors solution and explanation
Google
9 more videos on this problem
Two Furthest Houses With Different Colors | 4 Ways | Simple Explanation | Leetcode 2078 | MIKcodestorywithMIK · 18:42 · 4K views
2078. Two Furthest Houses With Different Colors (Leetcode Easy)Programming Live with Larry · 2:32 · 1K views
2078. Two Furthest Houses With Different Colors | LeetCode Easy | Python Solution | Array, GreedyShaheer Keerirakath · 2:25 · 785 views
LeetCode#2078 Two Furthest Houses With Different Colors - PythonCodeJulian · 2:07 · 774 views
LeetCode #2078 Two Furthest Houses With Different ColorsemptyStacks · 6:38 · 683 views
leetcode 2078 | Two Furthest Houses With Different Colors | Greedy | Leetcode POTDCode With Vick · 8:02 · 363 views
2078. Two Furthest Houses With Different Colors | Leetcode Daily - PythonLeetcode Daily · 5:21 · 326 views
Leetcode 2078 - Two Furthest Houses With Different ColorsAbhinav Kumar · 15:03 · 283 views
Two Furthest Houses With Different Colors | Leetcode 2078 | Approach + Code with explanation.Pirai's Academy · 10:51 · 183 views
Two Furthest Houses With Different Colors | LeetCode 2078Streak To Scale · 3:34 · 169 views
The 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:
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.length2 <= n <= 1000 <= colors[i] <= 100- Test data are generated such that at least two houses have different colors.
Approach overview
Problem Overview: You are given an array where each index represents a house and the value represents its color. The goal is to find the maximum distance |i - j| such that the colors of house i and house j are different. Since the distance is based on index difference, the optimal strategy focuses on comparing houses near the ends of the array where the potential distance is largest.
Approach 1: Two Pointer Technique (O(n) time, O(1) space)
This approach exploits the fact that the maximum distance must involve either the first or the last house. Start by comparing the first house with houses from the right end moving inward until a different color appears. Then compare the last house with houses from the left moving inward. The larger of these two distances is the answer. The key insight: if a house at one end has a different color from a far index, that pair already forms the maximum possible distance for that side. This technique works well because you only scan the array once while checking edge comparisons. The logic fits naturally into problems involving boundary scanning in array problems.
Approach 2: Single Loop with Reverse Check (O(n) time, O(1) space)
Another clean solution uses a single pass while comparing each element against the first and last houses. Iterate through the array and track the farthest index where the color differs from the first house. At the same time, check from the reverse side to find the farthest index where the color differs from the last house. This method effectively computes two candidate distances: i - 0 and (n - 1) - i. The maximum of these values becomes the answer. The approach behaves like a greedy scan because you always try to extend the distance as far as possible whenever a color mismatch appears. Problems like this often rely on simple boundary observations common in greedy and two pointer patterns.
Recommended for interviews: The two-pointer edge comparison approach is usually what interviewers expect. It shows that you recognized the maximum distance must involve the boundaries of the array. A brute-force O(n^2) comparison of every pair works but signals missed optimization opportunities. Demonstrating the O(n) boundary scan proves you understand how to reason about index distance and exploit array structure efficiently.
Approach 1: Two Pointer Technique
The main idea of this approach is to use a two-pointer technique: one pointer starting from the beginning of the array and the other from the end, and then calculate the distance between the first occurrence from the front and back with different colors.
This approach is efficient as it minimizes unnecessary comparisons by working inward from the boundaries which often gives maximum distances.
def maxDistance(colors):
n = len(colors)
max_dist = 0
for i in range(n):
if colors[i] != colors[0]:
max_dist = i
if colors[i] != colors[-1]:
dist_from_end = n - 1 - i
if dist_from_end > max_dist:
max_dist = dist_from_end
return max_dist
colors = [1, 8, 3, 8, 3]
print("Max distance:", maxDistance(colors))public class Solution {
public int maxDistance(int[] colors) {
int n = colors.length;
int maxDist = 0;
for (int i = 0; i < n; i++) {
if (colors[i] != colors[0]) {
maxDist = i;
}
if (colors[i] != colors[n - 1]) {
int distFromEnd = n - 1 - i;
if (distFromEnd > maxDist) {
maxDist = distFromEnd;
}
}
}
return maxDist;
}
public static void main(String[] args) {
int[] colors = {0, 1};
Solution sol = new Solution();
System.out.println("Max distance: " + sol.maxDistance(colors));
}
}#include <iostream>
#include <vector>
using namespace std;
int maxDistance(vector<int>& colors) {
int n = colors.size();
int max_dist = 0;
for(int i = 0; i < n; i++) {
if(colors[i] != colors[0]) {
max_dist = i;
}
if(colors[i] != colors[n-1]) {
int dist_from_end = n - 1 - i;
if(dist_from_end > max_dist) {
max_dist = dist_from_end;
}
}
}
return max_dist;
}
int main() {
vector<int> colors = {1, 8, 3, 8, 3};
cout << "Max distance: " << maxDistance(colors) << endl;
return 0;
}function maxDistance(colors) {
const n = colors.length;
let maxDist = 0;
for (let i = 0; i < n; i++) {
if (colors[i] !== colors[0]) {
maxDist = i;
}
if (colors[i] !== colors[n - 1]) {
const distFromEnd = n - 1 - i;
if (distFromEnd > maxDist) {
maxDist = distFromEnd;
}
}
}
return maxDist;
}
const colors = [1, 1, 1, 6, 1, 1, 1];
console.log("Max distance:", maxDistance(colors));#include <stdio.h>
#include <stdlib.h>
int maxDistance(int* colors, int colorsSize) {
int max_dist = 0;
for(int i = 0; i < colorsSize; i++) {
if(colors[i] != colors[0]) {
max_dist = i;
}
if(colors[i] != colors[colorsSize-1]) {
int dist_from_end = colorsSize - 1 - i;
if(dist_from_end > max_dist) {
max_dist = dist_from_end;
}
}
}
return max_dist;
}
int main() {
int colors[] = {1, 1, 1, 6, 1, 1, 1};
int n = sizeof(colors) / sizeof(colors[0]);
printf("Max distance: %d\n", maxDistance(colors, n));
return 0;
}using System;
public class Solution {
public int MaxDistance(int[] colors) {
int n = colors.Length;
int maxDist = 0;
for (int i = 0; i < n; i++) {
if (colors[i] != colors[0]) {
maxDist = i;
}
if (colors[i] != colors[n - 1]) {
int distFromEnd = n - 1 - i;
if (distFromEnd > maxDist) {
maxDist = distFromEnd;
}
}
}
return maxDist;
}
public static void Main() {
int[] colors = {1, 8, 3, 8, 3};
Solution sol = new Solution();
Console.WriteLine("Max distance: " + sol.MaxDistance(colors));
}
}Python code that relies on a linear pass over the colors array. It functions similarly to the C and C++ versions, calculating maximum distances from the first and last house with different color values.
Time Complexity: O(n).
Space Complexity: O(1).
Approach 2: Single Loop with Reverse Check
In this approach, the array is traversed from the beginning to find the first element different from the last one. In reverse, we also iterate from the end to find the first element different from the first one. The result is the maximum of these two measurements.
def maxDistance(colors):
i, j = 0, len(colors) - 1
while colors[i] == colors[-1]:
i += 1
while colors[0] == colors[j]:
j -= 1
return max(j, len(colors) - 1 - i)
colors = [1, 8, 3, 8, 3]
print("Max distance:", maxDistance(colors))public class Solution {
public int maxDistance(int[] colors) {
int i = 0, j = colors.length - 1;
while (colors[0] == colors[j]) j--;
while (colors[colors.length - 1] == colors[i]) i++;
return Math.max(colors.length - 1 - i, j);
}
public static void main(String[] args) {
int[] colors = {1, 8, 3, 8, 3};
Solution sol = new Solution();
System.out.println("Max distance: " + sol.maxDistance(colors));
}
}#include <iostream>
#include <vector>
using namespace std;
int maxDistance(vector<int>& colors) {
int i = 0, j = colors.size() - 1;
while (colors[0] == colors[j]) j--;
while (colors[colors.size() - 1] == colors[i]) i++;
return max(colors.size() - 1 - i, j);
}
int main() {
vector<int> colors = {1, 8, 3, 8, 3};
cout << "Max distance: " << maxDistance(colors) << endl;
return 0;
}function maxDistance(colors) {
let i = 0, j = colors.length - 1;
while (colors[0] === colors[j]) --j;
while (colors[colors.length - 1] === colors[i]) ++i;
return Math.max(colors.length - 1 - i, j);
}
const colors = [1, 1, 1, 6, 1, 1, 1];
console.log("Max distance:", maxDistance(colors));#include <stdio.h>
#include <stdlib.h>
int maxDistance(int* colors, int colorsSize) {
int i = 0, j = colorsSize - 1;
while (colors[0] == colors[j]) j--;
while (colors[colorsSize - 1] == colors[i]) i++;
return (colorsSize - 1 - i > j) ? colorsSize - 1 - i : j;
}
int main() {
int colors[] = {1, 8, 3, 8, 3};
int n = sizeof(colors) / sizeof(colors[0]);
printf("Max distance: %d\n", maxDistance(colors, n));
return 0;
}using System;
public class Solution {
public int MaxDistance(int[] colors) {
int i = 0, j = colors.Length - 1;
while (colors[0] == colors[j]) j--;
while (colors[colors.Length - 1] == colors[i]) i++;
return Math.Max(colors.Length - 1 - i, j);
}
public static void Main() {
int[] colors = {1, 8, 3, 8, 3};
Solution sol = new Solution();
Console.WriteLine("Max distance: " + sol.MaxDistance(colors));
}
}The Python solution uses two indices moving inward to rapidly determine divergences from both ends towards the middle.
Time Complexity: O(n).
Space Complexity: O(1).
Approach 3: Default Approach
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
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two Pointer Technique | Time Complexity: O(n). |
| Single Loop with Reverse Check | Time Complexity: O(n). |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pointer Technique | O(n) | O(1) | Best general solution. Quickly checks farthest distances from both array boundaries. |
| Single Loop with Reverse Check | O(n) | O(1) | Clean implementation when scanning the array once while tracking differences from first and last elements. |
Frequently asked questions
Is Two Furthest Houses With Different Colors easy or hard?
The problem is classified as Easy on LeetCode. The main challenge is recognizing that the maximum distance must involve one of the array boundaries rather than checking every pair of houses.
Two Furthest Houses With Different Colors Python/Java solution
Both Python and Java implementations follow the same logic: scan from both ends of the array and compute the maximum index difference when colors differ. The algorithm runs in O(n) time and requires constant space, making it efficient for large inputs.
How to solve Two Furthest Houses With Different Colors in O(n)?
Observe that the largest distance must involve either the first or last house. Scan the array to find the farthest index where the color differs from the first element, and similarly from the last element. The maximum of these two distances gives the result, producing an O(n) time and O(1) space solution.
What is the best approach for Two Furthest Houses With Different Colors?
The optimal approach is a greedy boundary scan using a two-pointer idea. Compare the first house with houses from the right side and the last house with houses from the left side. The maximum distance where colors differ is the answer. This runs in O(n) time and O(1) space.
Is Two Furthest Houses With Different Colors asked at Google/Amazon/Meta?
Array distance and greedy scanning problems appear frequently in interviews at companies like Amazon and Google. This specific problem tests whether you can recognize boundary-based optimization instead of brute-force pair comparisons.
What data structure is used in Two Furthest Houses With Different Colors?
The problem uses a simple array. No additional data structures such as hash maps or stacks are required. The solution relies on index comparisons and a greedy scan across the array.
What is the time complexity of Two Furthest Houses With Different Colors?
The optimal solution runs in O(n) time because the array is scanned once to check color differences from the boundaries. Space complexity is O(1) since only a few variables are used and no extra data structures are required.