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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Two Furthest Houses With Different Colors

Difficulty: Easy

Problem Description

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 i-th house. Return the maximum distance between two houses with different colors.

Key Insights

  • The distance between the i-th and j-th houses is calculated as abs(i - j).
  • To find the maximum distance, it's sufficient to only consider the first and last houses with different colors.
  • The result will be the maximum of the distances between the first house of one color and the last house of another color.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we can utilize a linear scan of the colors array to find the first and last occurrences of different colors. By checking the colors of the first and last houses, we can determine the maximum distance between houses of different colors. This approach only requires a single pass through the array, making it efficient.

Code Solutions

def maxDistance(colors):
    first_color = colors[0]
    last_color = colors[-1]
    max_distance = 0

    # Check distance from first house to last house of a different color
    for i in range(len(colors)):
        if colors[i] != first_color:
            max_distance = max(max_distance, i)
        if colors[i] != last_color:
            max_distance = max(max_distance, len(colors) - 1 - i)
    
    return max_distance
← Back to All Questions