Skip to main content
Talentd

Two Furthest Houses With Different Colors - Solution & Explanation

EasyArrayGreedy13 min readAsked at: Amazon, Meta, Visa +2
Practice this problem

Problem Statement

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.

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.

This C code solves the problem using a simple for loop to check against the first and last colors. We iterate through the array and check if there is a house with a different color from the first or last house. If found, we update the max distance accordingly.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), as we go through the list a constant number of times.
Space Complexity: O(1), using a constant amount of extra space.

Try this approach in the editor →

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.

This C code utilizes two simultaneous forward and backward searches to identify the furthest distinct colors. The loop ends as soon as it finds the distinct colors necessary for maximum separation.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) because of the single pass through the list.
Space Complexity: O(1), since no additional data structures are used.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Two Pointer Technique

Time Complexity: O(n), as we go through the list a constant number of times.
Space Complexity: O(1), using a constant amount of extra space.

Single Loop with Reverse Check

Time Complexity: O(n) because of the single pass through the list.
Space Complexity: O(1), since no additional data structures are used.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two Pointer TechniqueO(n)O(1)Best general solution. Quickly checks farthest distances from both array boundaries.
Single Loop with Reverse CheckO(n)O(1)Clean implementation when scanning the array once while tracking differences from first and last elements.

Video Solution

Two Furthest Houses With Different Colors | 4 Ways | Simple Explanation | Leetcode 2078 | MIK • codestorywithMIK • 4,575 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Two Furthest Houses With Different Colors with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Difference Between Increasing Elements

Next

Maximum Distance Between a Pair of Values