Two Furthest Houses With Different Colors

Easy

Visa

1 view

Topics:

Arrays

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.

The distance between the i^th and j^th 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.

Two Furthest Houses With Different Colors

Easy

Visa

1 view

Topics:

Arrays

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.

The distance between the i^th and j^th 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.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range of colors represented in the array (e.g., are they integers, strings, etc.), and are there any constraints on the number of distinct colors?
Is the input array guaranteed to have at least two houses, or should I handle the case where the array is empty or contains only one house?
If there are multiple pairs of houses with different colors that are equally far apart, should I return the distance of any one of those pairs?
Are the color values guaranteed to be valid and consistent, or do I need to handle cases where a color value is unexpected or null?
Is it guaranteed that there will be at least two houses with different colors in the input array?

Brute Force Solution

Approach

The brute force strategy to find the two furthest houses with different colors is all about trying every single combination. We systematically compare each house with every other house to check their colors.

Here's how the algorithm would work step-by-step:

Start by looking at the first house.
Compare the color of the first house to the color of every other house one by one.
If you find a house with a different color than the first one, calculate the distance between those two houses.
Keep track of the largest distance you've found so far between houses with different colors.
Move to the second house and repeat the process, comparing its color to every other house.
Again, update the largest distance if you find a larger one between houses with different colors.
Continue this process for every house, comparing it to every other house in the row.
After checking all possible pairs of houses, the largest distance you kept track of will be the distance between the two furthest houses with different colors.

Code Implementation

def furthest_houses_with_different_colors_brute_force(colors):
    max_distance = 0

    # Iterate through each house to compare it with every other
    for first_house_index in range(len(colors)):
        for second_house_index in range(len(colors)):

            # Check if colors of houses are different
            if colors[first_house_index] != colors[second_house_index]:

                # Update max_distance if current distance is larger
                current_distance = abs(first_house_index - second_house_index)
                max_distance = max(max_distance, current_distance)

    return max_distance

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The provided solution iterates through each of the n houses in the array. For each house, it then compares its color to every other house in the array, resulting in another iteration of potentially n comparisons in the worst case. This pair checking of all possible house combinations leads to nested loops, with the outer loop iterating n times and the inner loop iterating a maximum of n times. Thus, the total number of operations is proportional to n * n, which is O(n²).

Space Complexity

O(1) – The brute force algorithm, as described, iterates through the houses and compares their colors while keeping track of the maximum distance found. It only requires storing a few variables like the maximum distance encountered so far, and potentially indices of the houses. The number of these variables remains constant regardless of the number of houses, N. Therefore, the auxiliary space used by the algorithm is constant.

Optimal Solution

Approach

The core idea is to avoid checking every single pair of houses. Instead, we cleverly check only a few specific house pairings to find the largest possible distance between differently colored houses. We check the first house against the last and the last house against the first.

Here's how the algorithm would work step-by-step:

First, compare the color of the first house to the color of the last house.
If these colors are different, the distance between the first and last house is the answer, and we're done.
If the colors are the same, it means the furthest houses with different colors must be somewhere in between the first and last house.
Now, compare the color of the very last house to the colors of all houses moving inward from the beginning to find the house nearest the beginning with a different color. The distance between them is a possible answer.
Then, compare the color of the very first house to the colors of all houses moving inward from the end to find the house nearest the end with a different color. The distance between them is another possible answer.
Finally, take the larger of these two distances to find the maximum distance between two houses with different colors.

Code Implementation

def furthestHousesWithDifferentColors(colors):
    left_index = 0
    right_index = len(colors) - 1

    # If the first and last house colors differ, we have the answer.
    if colors[left_index] != colors[right_index]:
        return right_index - left_index

    max_distance = 0

    # Find the furthest house from the start with a different color
    for index in range(right_index - 1, 0, -1):

        if colors[left_index] != colors[index]:
            max_distance = max(max_distance, index - left_index)

            break

    # Find the furthest house from the end with a different color
    for index in range(1, right_index):

        if colors[right_index] != colors[index]:
            max_distance = max(max_distance, right_index - index)

            break

    return max_distance

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm first compares the first and last houses, which is O(1). In the worst case, it then iterates from the beginning to the end and from the end to the beginning to find the closest houses with different colors. These two iterations are at most n steps combined. Thus, the time complexity is dominated by the single loops, resulting in O(n).

Space Complexity

O(1) – The algorithm's space complexity is O(1) because it only uses a few constant space variables to store indices and calculate distances. No auxiliary data structures like arrays, hash maps, or recursion stacks are created. The amount of extra memory used does not depend on the number of houses, N, making it constant space complexity.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately, as no houses exist to compare.
Array with only one house	Return 0, since no other house exists to have a different color.
Array with only two houses of different colors, located at the extremes.	The algorithm should correctly identify these houses and return the distance which is colors.length - 1.
All houses have the same color	Return 0, as there are no two houses with different colors.
Houses are arranged such that different colors are clustered together with the same color filling the end of array	The algorithm should correctly traverse the array from both ends to find the furthest apart differently colored houses.
Integer overflow if array size is close to Integer.MAX_VALUE	The problem states max size is 100, so integer overflow isn't a concern with the length of the array, but consider checking distance calculation to ensure no int overflow
Large input size	The solution should have a time complexity of O(n) to ensure it scales efficiently with larger input sizes.
Edge case with extreme boundary values of color values	Since the array only contains colors, the boundary values don't have any special effect other than the equality comparison. No special handling required.