Introduction

In this blog post, we will explore how to solve the LeetCode problem "2078" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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 ith house. Return the maximum distance between two houses with different colors. The distance between the ith and jth 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.

Explanation

Here's an efficient solution to find the maximum distance between two houses with different colors, along with an explanation:

• High-Level Approach:

  • Iterate from the beginning to find the farthest house with a different color than the first house.
  • Iterate from the end to find the farthest house with a different color than the last house.
  • Return the maximum of the two distances.

• Complexity:

  • Runtime: O(n)
  • Storage: O(1)

Code

    def maxDistance(colors):
    """
    Finds the maximum distance between two houses with different colors.

    Args:
        colors: A list of integers representing the colors of the houses.

    Returns:
        The maximum distance between two houses with different colors.
    """
    n = len(colors)
    max_dist = 0

    # Find farthest house from the beginning
    for i in range(n - 1, 0, -1):
        if colors[i] != colors[0]:
            max_dist = max(max_dist, i - 0)
            break

    # Find farthest house from the end
    for i in range(0, n - 1):
        if colors[i] != colors[n - 1]:
            max_dist = max(max_dist, n - 1 - i)
            break

    return max_dist