We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Two Furthest Houses With Different Colors

Number: 2199

Difficulty: Easy

Paid? No

Companies: Visa

Problem Description

Given an array where each element represents the color of a house aligned in a row, determine the maximum distance (absolute difference of indices) between two houses that have different colors.

Key Insights

  • The maximum possible distance is between the first and last house in the array.
  • If the first and last house are painted in different colors, the answer is simply the length of the array minus one.
  • If they are the same, search inward from both ends to locate the furthest house with a different color.
  • Since there is a guarantee that at least two houses are painted differently, one of these checks will always provide the maximum distance.

Space and Time Complexity

Time Complexity: O(n) because we are scanning the array at most twice. Space Complexity: O(1) since only a few extra variables are used.

Solution

The solution first checks the two end houses. If their colors are different, the maximum distance is the array length minus one. If they are the same, the solution performs two passes: one starting from the right side to find the first house with a different color from the first house, and one starting from the left side to find the first house with a different color from the last house. The maximum of these two distances is returned. This approach avoids checking every possible pair and guarantees optimal performance.

Code Solutions

# Function to compute the maximum distance between two houses with different colors.
def max_distance(colors):
    n = len(colors)
    # Check if the first and last houses are of different colors.
    if colors[0] != colors[n - 1]:
        return n - 1

    max_dist = 0
    # Traverse from the right to find the first index where the color differs from the first house.
    for i in range(n - 1, -1, -1):
        if colors[i] != colors[0]:
            max_dist = max(max_dist, i)
            break

    # Traverse from the left to find the first index where the color differs from the last house.
    for i in range(n):
        if colors[i] != colors[n - 1]:
            max_dist = max(max_dist, n - 1 - i)
            break

    return max_dist

# Example usage:
print(max_distance([1, 1, 1, 6, 1, 1, 1]))  # Output: 3
print(max_distance([1, 8, 3, 8, 3]))         # Output: 4
print(max_distance([0, 1]))                  # Output: 1
← Back to All Questions