Two Furthest Houses With Different Colors

Two Furthest Houses With Different Colors

What is this problem about?

The "Two Furthest Houses With Different Colors coding problem" asks you to find the maximum possible distance between any two houses in a row that have different colors. You are given an array where each element is an integer representing a color. The distance between two indices i and j is simply |i - j|. The goal is to find the largest such distance among all valid pairs of houses.

Why is this asked in interviews?

This is a common "EASY" problem at Google and Visa because it rewards a "Greedy" insight over a brute-force $O(N^2)$ approach. It tests whether a candidate can identify that the optimal solution must involve one of the houses at the extreme ends of the array. It's a great way to gauge if a developer looks for $O(N)$ optimizations even for simple tasks.

Algorithmic pattern used

The "Array, Greedy interview pattern" is used here. Because we want to maximize the distance, the best candidates for the pair are the first house and the last house.

1. Check the first house against all houses starting from the right. The first house with a different color gives a potential maximum distance.
2. Check the last house against all houses starting from the left. The first house with a different color gives another potential maximum distance. The overall maximum is the higher of these two values.

Example explanation

Colors: [1, 8, 3, 8, 1]

• First house is 1. Starting from the right:
  • Last house (index 4) is 1. (Same color, skip)
  • Index 3 is 8. (Different color!) Distance = $3 - 0 = 3$.
• Last house is 1. Starting from the left:
  • First house (index 0) is 1. (Same color, skip)
  • Index 1 is 8. (Different color!) Distance = $4 - 1 = 3$. Result: 3. If the colors were [1, 8, 3, 3, 3], comparing the first house (1) and the last house (3) would immediately give a distance of 4.

Common mistakes candidates make

The biggest pitfall is using a nested loop, which makes the time complexity $O(N^2)$. While correct, it's inefficient for large house arrays. Another mistake is assuming that the first and last houses must be different colors, which isn't always true. You must be able to handle cases where the ends are the same color by looking for the next best candidate.

Interview preparation tip

When solving the "Two Furthest Houses With Different Colors interview question," always consider the "Extreme Boundaries." In array problems involving maximum distance or span, the elements at index 0 and index $n-1$ are almost always involved in the optimal solution.