What is the time complexity of the Brute Force approach?

The time complexity of the Brute Force approach is O(n²), where n is the number of houses.

What is the time complexity of the Greedy Linear Scan approach?

The time complexity of the Greedy Linear Scan approach is O(n), where n is the number of houses.

What is the space complexity of the Greedy Linear Scan approach?

The space complexity of the Greedy Linear Scan approach is O(1), as it uses a constant amount of extra space.

Two Furthest Houses With Different Colors

Difficulty: Easy | Acceptance: 71.80% | Paid: No Topics: Array, Greedy

There is a street of n houses represented by an array colors where colors[i] represents the color of the ith house.

Return the maximum distance between two houses with different colors.

The distance between the ith and jth houses is abs(i - j).

Examples

Example 1:

Input: colors = [1,1,1,6,1,1,1] Output: 3 Explanation: The house at index 0 has color 1, and the house at index 3 has color 6. The distance between them is abs(0 - 3) = 3. Note that houses 3 and 6 can also produce the maximum distance.

Example 2:

Input: colors = [1,8,3,8,3] Output: 4 Explanation: The house at index 0 has color 1, and the house at index 4 has color 3. The distance between them is abs(0 - 4) = 4.

Example 3:

Input: colors = [0,0,0,0,0] Output: 0 Explanation: Since all houses have the same color, no two houses with different colors can be chosen. Thus, the maximum distance is 0.

Constraints

n == colors.length
2 <= n <= 100
0 <= colors[i] <= 100

Brute Force

Intuition Check every possible pair of houses to see if they have different colors and keep track of the maximum distance found.

Steps

Initialize a variable maxDist to 0.
Iterate through the array with index i from 0 to n-1.
Iterate through the array with index j from i+1 to n-1.
If colors[i] is not equal to colors[j], update maxDist with the maximum of maxDist and j - i.
Return maxDist.

python

class Solution:
    def maxDistance(self, colors: list[int]) -&gt; int:
        n = len(colors)
        max_dist = 0
        for i in range(n):
            for j in range(i + 1, n):
                if colors[i] != colors[j]:
                    max_dist = max(max_dist, j - i)
        return max_dist

Complexity

Time: O(n²) where n is the length of the array.
Space: O(1)
Notes: Simple to implement but inefficient for large arrays.

Greedy Linear Scan

Intuition The maximum distance must involve either the first house or the last house. If the first house has a different color than the last house, the distance is n-1. If not, the furthest house from the first house with a different color, or the furthest house from the last house with a different color, will yield the maximum distance.

Steps

Initialize maxDist to 0.
Iterate from the start of the array to the end. If the current house color is different from the first house color, update maxDist with the current index.
Iterate from the end of the array to the start. If the current house color is different from the last house color, update maxDist with the distance from the end (n - 1 - current index).
Return maxDist.

python

class Solution:
    def maxDistance(self, colors: list[int]) -&gt; int:
        n = len(colors)
        max_dist = 0
        
        # Compare with the first house
        for i in range(n):
            if colors[i] != colors[0]:
                max_dist = max(max_dist, i)
                
        # Compare with the last house
        for i in range(n - 1, -1, -1):
            if colors[i] != colors[-1]:
                max_dist = max(max_dist, n - 1 - i)
                
        return max_dist

Complexity

Time: O(n) where n is the length of the array.
Space: O(1)
Notes: Optimal solution with linear time complexity.