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] <= 100Problem 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.
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.
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.
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.
Time Complexity: O(n) because of the single pass through the list.
Space Complexity: O(1), since no additional data structures are used.
| Approach | Complexity |
|---|---|
| Two Pointer Technique | Time Complexity: O(n), as we go through the list a constant number of times. |
| Single Loop with Reverse Check | Time Complexity: O(n) because of the single pass through the list. |
| Default Approach | — |
| 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. |
Leetcode Weekly Contest 268, (Easy)2078. Two Furthest Houses With Different Colors • Competitive Somya • 1,556 views views
Watch 9 more video solutions →Practice Two Furthest Houses With Different Colors with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor