Two Furthest Houses With Different Colors — Solution
Two Furthest Houses With Different Colors solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Two Furthest Houses With Different Colors is an easy coding problem on arrays and greedy, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Arrays, Greedy
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
n houses stand in a row, and colors[i] is the colour of house i. The distance between houses i and j is |i - j|.
Return the largest distance between two houses of different colours. At least two houses have different colours.
Example 1
Input: colors = [2,2,5,2,2]
Output: 2
Explanation: House 2 is the only one with colour 5; it is 2 away from both ends.
Example 2
Input: colors = [4,8]
Output: 1
Example 3
Input: colors = [3,1,3,3,3,3]
Output: 4
Explanation: Houses 1 and 5.
Constraints
2 <= n <= 100n == colors.length0 <= colors[i] <= 100At least two houses have different colours
Hints for Two Furthest Houses With Different Colors
Hint 1
One end of the best pair can always be the first house or the last house.
Hint 2
If the first and last houses differ, the answer is
n - 1.Hint 3
Otherwise compare: the furthest house from the left end whose colour differs from
colors[0], and the furthest house from the right end whose colour differs fromcolors[n - 1].
How to solve Two Furthest Houses With Different Colors
An optimal pair can always be stretched to touch an end of the row, so only pairs involving house 0 or house n - 1 need checking.
Approach
- Find the largest
jwithcolors[j] != colors[0]; it gives distancej. - Find the smallest
iwithcolors[i] != colors[n - 1]; it gives distancen - 1 - i. - Return the larger of the two.
Why it works
Take an optimal pair i < j. If colors[j] != colors[0], the pair (0, j) is at least as long, and the first scan finds some j' >= j. If colors[i] != colors[n - 1], the pair (i, n - 1) is at least as long, and the second scan finds some i' <= i. Otherwise colors[0] == colors[j] and colors[n - 1] == colors[i], so the two ends differ and the first scan already returns n - 1, the largest distance there is.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Checking only pairs that use house 0 returns 1 on
[2,1,2,2,2], whose answer is 3 — scan from both ends. - The brute-force double loop is fine for n ≤ 100, but the end-anchored scan is O(n).
- Colours may be 0, so do not use 0 as a 'no colour' sentinel.
Reference solution
Python
from typing import List
def maxDistance(colors: List[int]) -> int:
n = len(colors)
best = 0
for j in range(n - 1, -1, -1):
if colors[j] != colors[0]:
best = j
break
for i in range(n):
if colors[i] != colors[n - 1]:
best = max(best, n - 1 - i)
break
return bestJava
public static int maxDistance(int[] colors) {
int n = colors.length, best = 0;
for (int j = n - 1; j >= 0; j--) {
if (colors[j] != colors[0]) { best = j; break; }
}
for (int i = 0; i < n; i++) {
if (colors[i] != colors[n - 1]) { best = Math.max(best, n - 1 - i); break; }
}
return best;
}C++
int maxDistance(vector<int>& colors) {
int n = colors.size(), best = 0;
for (int j = n - 1; j >= 0; j--) {
if (colors[j] != colors[0]) { best = j; break; }
}
for (int i = 0; i < n; i++) {
if (colors[i] != colors[n - 1]) { best = max(best, n - 1 - i); break; }
}
return best;
}JavaScript
var maxDistance = function(colors) {
var n = colors.length, best = 0;
for (var j = n - 1; j >= 0; j--) {
if (colors[j] !== colors[0]) { best = j; break; }
}
for (var i = 0; i < n; i++) {
if (colors[i] !== colors[n - 1]) { best = Math.max(best, n - 1 - i); break; }
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Greedy Algorithms