Problem Description

You are given an array colors representing n houses lined up on a street, where colors[i] indicates the color of the i-th house (0-indexed). Your task is to find the maximum distance between any two houses that have different colors.

The distance between two houses at positions i and j is calculated as abs(i - j), which is the absolute difference between their indices.

For example, if colors = [1, 1, 2, 3, 1]:

• House at index 0 (color 1) and house at index 2 (color 2) have distance abs(0 - 2) = 2
• House at index 0 (color 1) and house at index 3 (color 3) have distance abs(0 - 3) = 3
• House at index 1 (color 1) and house at index 2 (color 2) have distance abs(1 - 2) = 1

The solution uses a brute force approach with two nested loops. The outer loop iterates through each house at position i, and the inner loop checks all houses at positions j > i. When two houses have different colors (colors[i] != colors[j]), the distance between them is calculated and compared with the current maximum distance. The algorithm keeps track of and returns the maximum distance found between any pair of houses with different colors.

The time complexity is O(n²) due to the nested loops checking all pairs of houses, and the space complexity is O(1) as only a constant amount of extra space is used.

Intuition

The key observation is that we need to find the maximum distance between any two houses with different colors. Since distance is defined as the absolute difference between indices, we want to find two houses with different colors that are as far apart as possible on the street.

The most straightforward way to think about this problem is to check every possible pair of houses. For each house, we can compare it with every other house to see if they have different colors. If they do, we calculate their distance and keep track of the maximum distance found so far.

Why does this brute force approach work? Because:

1. We need to ensure we don't miss any potential pair that could give us the maximum distance
2. The constraint that houses must have different colors means we can't simply take the first and last house (they might have the same color)
3. The maximum distance could occur between any two houses in the array, not necessarily at the extremes

For each house at position i, we only need to check houses at positions j > i because:

• The distance abs(i - j) is the same as abs(j - i)
• Checking both (i, j) and (j, i) would be redundant

This leads us naturally to the nested loop solution: iterate through each house with the outer loop, and for each house, check all subsequent houses with the inner loop. Whenever we find a pair with different colors, we update our maximum distance if this pair is farther apart than any previous pair we've found.

Learn more about Greedy patterns.

Solution Approach

The solution implements a brute force approach using nested loops to find the maximum distance between houses with different colors.

Algorithm Steps:

1. Initialize variables: Set ans = 0 to track the maximum distance found, and get the length of the array n = len(colors).

2. Outer loop: Iterate through each house index i from 0 to n-1. This represents the first house in each potential pair.

3. Inner loop: For each house i, iterate through all subsequent houses with index j from i+1 to n-1. This ensures we check all pairs exactly once without redundancy.

4. Check color difference: For each pair (i, j), check if colors[i] != colors[j]. Only proceed if the houses have different colors.

5. Update maximum: When different colors are found, calculate the distance as abs(i - j) and update ans using max(ans, abs(i - j)). This keeps track of the largest distance encountered so far.

6. Return result: After checking all possible pairs, return ans as the maximum distance.

Implementation Details:

• Since j always starts from i+1 and goes up to n-1, we know that j > i, which means abs(i - j) = j - i. However, the code uses abs() for clarity.
• The max() function ensures we only keep the largest distance value.
• The algorithm examines n * (n-1) / 2 pairs in total, giving us O(n²) time complexity.

Example Walkthrough:

For colors = [1, 2, 1, 2]:

• i=0, j=1: colors are different (1≠2), distance = 1, ans = 1
• i=0, j=2: colors are same (1=1), skip
• i=0, j=3: colors are different (1≠2), distance = 3, ans = 3
• i=1, j=2: colors are different (2≠1), distance = 1, ans remains 3
• i=1, j=3: colors are same (2=2), skip
• i=2, j=3: colors are different (1≠2), distance = 1, ans remains 3
• Return 3

Example Walkthrough

Let's walk through the solution with colors = [2, 2, 3, 2, 3]:

Initial Setup:

• ans = 0 (tracks maximum distance)
• n = 5 (array length)

Iteration Process:

When i = 0 (house with color 2):

• j = 1: colors[0] = 2, colors[1] = 2 → Same color, skip
• j = 2: colors[0] = 2, colors[2] = 3 → Different! Distance = |0-2| = 2, update ans = 2
• j = 3: colors[0] = 2, colors[3] = 2 → Same color, skip
• j = 4: colors[0] = 2, colors[4] = 3 → Different! Distance = |0-4| = 4, update ans = 4

When i = 1 (house with color 2):

• j = 2: colors[1] = 2, colors[2] = 3 → Different! Distance = |1-2| = 1, ans stays 4
• j = 3: colors[1] = 2, colors[3] = 2 → Same color, skip
• j = 4: colors[1] = 2, colors[4] = 3 → Different! Distance = |1-4| = 3, ans stays 4

When i = 2 (house with color 3):

• j = 3: colors[2] = 3, colors[3] = 2 → Different! Distance = |2-3| = 1, ans stays 4
• j = 4: colors[2] = 3, colors[4] = 3 → Same color, skip

When i = 3 (house with color 2):

• j = 4: colors[3] = 2, colors[4] = 3 → Different! Distance = |3-4| = 1, ans stays 4

Result: The maximum distance found is 4 (between houses at indices 0 and 4).

The algorithm successfully identifies that the farthest apart houses with different colors are at positions 0 and 4, both having different colors (2 and 3 respectively), giving us the maximum possible distance of 4.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²)

The code uses two nested loops:

• The outer loop iterates through all indices from 0 to n-1, where n is the length of the colors array
• The inner loop iterates from i+1 to n-1 for each iteration of the outer loop
• This creates approximately n * (n-1) / 2 total iterations, which simplifies to O(n²)
• Inside the loops, the operations (comparison, max calculation, and absolute value) are all O(1)

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space:

• Variable ans to store the maximum distance found
• Variable n to store the length of the array
• Loop variables i and j
• No additional data structures are created that scale with the input size

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Inefficient Time Complexity for Large Arrays

The brute force O(n²) approach becomes inefficient when dealing with large arrays. Since we're checking every possible pair, this can lead to Time Limit Exceeded (TLE) errors on platforms with strict time constraints.

Solution: Optimize using a greedy approach that only checks houses at the extremes:

def maxDistance(self, colors: List[int]) -> int:
    n = len(colors)
    max_dist = 0
  
    # Fix first house, find furthest house with different color from the end
    for j in range(n - 1, -1, -1):
        if colors[0] != colors[j]:
            max_dist = max(max_dist, j)
            break
  
    # Fix last house, find furthest house with different color from the start
    for i in range(n):
        if colors[n - 1] != colors[i]:
            max_dist = max(max_dist, n - 1 - i)
            break
  
    return max_dist

This optimized solution runs in O(n) time by recognizing that the maximum distance must involve either the first or last house.

2. Redundant Absolute Value Calculation

Using abs(i - j) when we know j > i is unnecessary since the result will always be j - i.

Solution: Simply use j - i instead:

if colors[i] != colors[j]:
    max_distance = max(max_distance, j - i)

3. Not Handling Edge Cases

Failing to consider arrays where all houses have the same color (though the problem typically guarantees at least two different colors exist).

Solution: Add validation if needed:

def maxDistance(self, colors: List[int]) -> int:
    if len(set(colors)) == 1:
        return 0  # All houses have the same color
  
    # Rest of the implementation...

4. Starting Inner Loop from Wrong Index

A common mistake is starting the inner loop from j = 0 or j = i, which either causes duplicate comparisons or misses the i+1 starting point.

Solution: Always ensure the inner loop starts from i + 1:

for i in range(n):
    for j in range(i + 1, n):  # Correct: starts from i+1
        # Process pair (i, j)