algoadvance

You are given an integer array colors of length n, where there are n houses in a row. The ith house has a color represented by colors[i]. Return the maximum distance between two houses with different colors.

Constraints

• n == colors.length
• 2 <= n <= 100
• 0 <= colors[i] <= 100
• colors[i] != colors[i+1] for all valid i

Example

Input: colors = [1,1,1,6,1,1,1]
Output: 3
Explanation: The maximum distance is between house 0 (color 1) and house 3 (color 6).

Input: colors = [1,8,3,8,3]
Output: 4
Explanation: The maximum distance is between house 0 (color 1) and house 4 (color 3).

Input: colors = [0,1]
Output: 1

Clarifying Questions

1. Are the color values guaranteed to be integers within [0,100] range?
   • Yes.
2. Can the list of colors contain only two houses?
   • Yes, the minimum length of the list can be 2.

Strategy

To find the two furthest houses with different colors, we can follow these steps:

1. Initialize two pointers, one starting from the beginning (left) and one from the end (right).
2. Check pairs formed by mixing these two:
   • Start with left fixed at the beginning and right moving towards the left, stop when you find the first different color.
   • Start with right fixed at the end and left moving towards the right, stop when you find the first different color.
3. Record the two distances found from the above checks.
4. The maximum of these two distances is our result.

Code

def maxDistance(colors):
    n = len(colors)
    left = 0
    right = n - 1
    
    # Check from the left end moving to the right
    while colors[left] == colors[right]:
        right -= 1
    max_dist_from_left = right

    # Check from the right end moving to the left
    left = 0
    while colors[left] == colors[n-1]:
        left += 1
    max_dist_from_right = n-1 - left

    return max(max_dist_from_left, max_dist_from_right)

# Test examples
print(maxDistance([1,1,1,6,1,1,1]))  # Output: 3
print(maxDistance([1,8,3,8,3]))      # Output: 4
print(maxDistance([0,1]))            # Output: 1

Time Complexity

• Time Complexity: O(n)
  • In the worst case, we might scan the list two times, which results in a linear time complexity O(n).
• Space Complexity: O(1)
  • We are using constant space to store the indices and the distances.

By efficiently scanning from both ends of the list, we ensure that the maximum distance is found with minimal complexity.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?