Two Furthest Houses With Different Colors - Video Solutions

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.