Skip to content

2078. Two Furthest Houses With Different Colors 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
 public:
  int maxDistance(vector<int>& colors) {
    // The maximum distance always includes either the first or the last house.
    const int n = colors.size();
    int i = 0;      // the leftmost index, where colors[i] != colors[-1]
    int j = n - 1;  // the rightmost index, where colors[j] != colors[0]
    while (colors[i] == colors.back())
      ++i;
    while (colors[j] == colors.front())
      --j;
    return max(n - 1 - i, j);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
  public int maxDistance(int[] colors) {
    final int n = colors.length;
    int i = 0;     // the leftmost index, where colors[i] != colors[n - 1]
    int j = n - 1; // the rightmost index, where colors[j] != colors[0]
    while (colors[i] == colors[n - 1])
      ++i;
    while (colors[j] == colors[0])
      --j;
    return Math.max(n - 1 - i, j);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
  def maxDistance(self, colors: List[int]) -> int:
    # The maximum distance always includes either the first or the last house.
    n = len(colors)
    i = 0  # the leftmost index, where colors[i] != colors[-1]
    j = n - 1  # the rightmost index, where colors[j] != colors[0]
    while colors[i] == colors[-1]:
      i += 1
    while colors[j] == colors[0]:
      j -= 1
    return max(n - 1 - i, j)