Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2078.html
2078. Two Furthest Houses With Different Colors (Easy)
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.
Similar Questions:
- Replace Elements with Greatest Element on Right Side (Easy)
- Maximum Distance Between a Pair of Values (Medium)
- Maximum Difference Between Increasing Elements (Easy)
Solution 1. Map
For each A[i]
:
- If this is the first occurrence of this value, store
A[i] -> i
in a mapm
. - Loop through each
num, index
pair the mapm
and calculate the maximumi - index
value ifnum != A[i]
.
-
// OJ: https://leetcode.com/problems/two-furthest-houses-with-different-colors/ // Time: O(NM) where `N` is the length of `A` and `M` is the range of numbers in `A`. // Space: O(M) class Solution { public: int maxDistance(vector<int>& A) { unordered_map<int, int> m; // first occurrence index int ans = 0; for (int i = 0; i < A.size(); ++i) { if (m.count(A[i]) == 0) m[A[i]] = i; for (auto &[c, j] : m) { if (c != A[i]) { ans = max(ans, i - j); } } } return ans; } };
-
// Todo
-
class Solution: def maxDistance(self, colors: List[int]) -> int: n = len(colors) if colors[0] != colors[-1]: return n - 1 i, j = 1, n - 2 while colors[i] == colors[0]: i += 1 while colors[j] == colors[0]: j -= 1 return max(n - i - 1, j) ############ # 2078. Two Furthest Houses With Different Colors # https://leetcode.com/problems/two-furthest-houses-with-different-colors/ class Solution: def maxDistance(self, colors: List[int]) -> int: n = len(colors) res = 0 for i in range(n): for j in range(i + 1, n): if colors[i] != colors[j]: res = max(res, abs(j - i)) return res
Or use array.
-
// OJ: https://leetcode.com/problems/two-furthest-houses-with-different-colors/ // Time: O(NM) where `N` is the length of `A` and `M` is the range of numbers in `A`. // Space: O(M) class Solution { public: int maxDistance(vector<int>& A) { int ans = 0, index[101] = {[0 ... 100] = -1}; for (int i = 0; i < A.size(); ++i) { if (index[A[i]] == -1) index[A[i]] = i; for (int j = 0; j <= 100; ++j) { if (index[j] != -1 && j != A[i]) { ans = max(ans, i - index[j]); } } } return ans; } };
-
// Todo
-
class Solution: def maxDistance(self, colors: List[int]) -> int: n = len(colors) if colors[0] != colors[-1]: return n - 1 i, j = 1, n - 2 while colors[i] == colors[0]: i += 1 while colors[j] == colors[0]: j -= 1 return max(n - i - 1, j) ############ # 2078. Two Furthest Houses With Different Colors # https://leetcode.com/problems/two-furthest-houses-with-different-colors/ class Solution: def maxDistance(self, colors: List[int]) -> int: n = len(colors) res = 0 for i in range(n): for j in range(i + 1, n): if colors[i] != colors[j]: res = max(res, abs(j - i)) return res
Solution 2. Mono-increasing Index Array
For each A[i]
:
- If this is the first occurrence of this value, push
i
into avector<int> index
. - Loop through each index value
j
inindex
array, and update answer withi - j
for the firstA[j] != A[i]
. This step at most looks at two indices, so it’sO(1)
time.
-
// OJ: https://leetcode.com/problems/two-furthest-houses-with-different-colors/ // Time: O(N) where `N` is the length of `A` and `M` is the range of numbers in `A`. // Space: O(M) class Solution { public: int maxDistance(vector<int>& A) { vector<int> index; // first occurrence index int ans = 0, seen[101] = {}; for (int i = 0; i < A.size(); ++i) { if (!seen[i]) { seen[i] = 1; index.push_back(i); } for (int j : index) { if (A[j] != A[i]) { ans = max(ans, i - j); break; } } } return ans; } };
-
// Todo
-
class Solution: def maxDistance(self, colors: List[int]) -> int: n = len(colors) if colors[0] != colors[-1]: return n - 1 i, j = 1, n - 2 while colors[i] == colors[0]: i += 1 while colors[j] == colors[0]: j -= 1 return max(n - i - 1, j) ############ # 2078. Two Furthest Houses With Different Colors # https://leetcode.com/problems/two-furthest-houses-with-different-colors/ class Solution: def maxDistance(self, colors: List[int]) -> int: n = len(colors) res = 0 for i in range(n): for j in range(i + 1, n): if colors[i] != colors[j]: res = max(res, abs(j - i)) return res
Discuss
https://leetcode.com/problems/two-furthest-houses-with-different-colors/discuss/1589010/C%2B%2B-O(N)-Time-One-Pass